laboratoare:02-functii-de-ordin-superior
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
laboratoare:02-functii-de-ordin-superior [2016/03/06 21:35] calin.cruceru [Combinatori și închideri funcționale] |
laboratoare:02-functii-de-ordin-superior [2016/03/06 23:34] (current) mihai.dumitru2201 |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Funcții ====== | ====== Funcții ====== | ||
| - | * Semnificatia termenului //aplicatie// | + | Responsabili laborator: |
| - | * Definirea **functiilor anonime** in Haskell: | + | * [[mihai.dumitru@cti.pub.ro|Dumitru Mihai-Valentin]] |
| - | <code haskell> \x1 x2 ... -> expr </code> | + | * [[calin.cruceru@cti.pub.ro|Călin Cruceru]] |
| - | * Curry vs uncurry (si de ce nu conteaza in Haskell) | + | |
| - | * **Inchideri functionale**: | + | |
| - | * definiti o functie care prefixeaza [1,2,3] la o lista primita ca parametru, ca o inchidere functionala | + | |
| + | Scopul laboratorului: | ||
| + | * Semnificația termenului //aplicație// | ||
| + | * Definirea funcțiilor anonime în Haskell | ||
| + | * Curry vs uncurry (și de ce nu contează în Haskell) | ||
| + | * Închideri funcționale | ||
| ===== Funcții de ordin superior ===== | ===== Funcții de ordin superior ===== | ||
| Line 14: | Line 16: | ||
| Pentru a înțelege importanța lor, vom da următorul exemplu: ne propunem să scriem două funcții care primesc o listă și returnează, într-o nouă listă | Pentru a înțelege importanța lor, vom da următorul exemplu: ne propunem să scriem două funcții care primesc o listă și returnează, într-o nouă listă | ||
| * toate elementele pare | * toate elementele pare | ||
| - | * toate elementele mai mari ca 10 | + | * toate elementele mai mari decât 10 |
| <code haskell> | <code haskell> | ||
| Line 69: | Line 71: | ||
| ===== Currying vs. uncurrying ===== | ===== Currying vs. uncurrying ===== | ||
| - | Currying este o tehnică (numită după [[https://en.wikipedia.org/wiki/Haskell_Curry|tizul Haskell-ului]]) prin care, dintr-o funcție care ia mai multe argumente, se obține o secvență de funcții care iau un singur argument. | + | Currying (numit după [[https://en.wikipedia.org/wiki/Haskell_Curry|tizul Haskell-ului]]) este procesul prin care, dintr-o funcție care ia mai multe argumente, se obține o secvență de funcții care iau un singur argument. |
| - | De exemplu, dintr-o funcție de două argumente ''f : X × Y → Z'' se obține o funcție ''curry(f) : X → (Y → Z)''. Noua funcție ''curry(f)'' primește un argument de tipul ''X'' și întoarce o funcție de tipul ''Y → Z'' (adică o funcție care primește un argument de tipul ''Y'' și întoarce un rezultat de tip ''Z''). Considerând operatorul ''→'' asociativ la dreapta, putem omite parantezele, i.e. ''curry(f) : X → Y → Z''. | + | De exemplu, dintr-o funcție de două argumente ''f : X × Y → Z'' se obține o funcție\\ |
| + | ''curry(f) : X → (Y → Z)''. Noua funcție ''curry(f)'' primește un argument de tipul ''X'' și întoarce o funcție de tipul ''Y → Z'' (adică o funcție care primește un argument de tipul ''Y'' și întoarce un rezultat de tip ''Z''). Considerând operatorul ''→'' asociativ la dreapta, putem omite parantezele, i.e. ''curry(f) : X → Y → Z''. | ||
| Operația inversă se numește "uncurry": ''f : X → Y → Z, uncurry(f): X × Y → Z''. | Operația inversă se numește "uncurry": ''f : X → Y → Z, uncurry(f): X × Y → Z''. | ||
| + | |||
| + | Întorcându-ne la funcția de filtrare definită mai devreme, care este tipul ei? | ||
| + | |||
| + | <code> | ||
| + | *Main> :t myFilter | ||
| + | myFilter :: (a -> Bool) -> [a] -> [a] | ||
| + | </code> | ||
| + | |||
| + | Și în [[laboratoare:01-functii-recursive#definirea_unei_functii|laboratorul trecut]], am observat că nu există o separare între domeniu și codomeniu, de genul\\ | ||
| + | ''(a -%%>%% Bool) x [a] -%%>%% [a]''. | ||
| + | |||
| + | <note important> | ||
| + | Acest lucru se datorează faptului că, în Haskell, **toate funcțiile iau un singur argument**. Alternativ, putem spune despre ele că sunt //curried//. | ||
| + | |||
| + | Tipul funcției noastre trebuie interpretat astfel:\\ | ||
| + | primește ca argument o funcție de tipul ''a -%%>%% Bool'' (ia un argument și întoarce o booleană) și întoarce o funcție de tipul ''[a] -%%>%% [a]'' (ia o listă și întoarce o listă de același tip). | ||
| + | |||
| + | De aceea, în exemplul de mai sus am putut definit ''evenElements'' (o funcție care ia o listă și returnează o listă) ca fiind ''myFilter even'' care are exact acest tip, i.e. ''[a] -%%>%% [a]''. | ||
| + | </note> | ||
| + | |||
| + | <note> | ||
| + | Haskell pune la dispoziție funcțiile ''curry'' și ''uncurry''. | ||
| + | |||
| + | <code> | ||
| + | *Main> :t curry | ||
| + | curry :: ((a, b) -> c) -> a -> b -> c | ||
| + | *Main> :t uncurry | ||
| + | uncurry :: (a -> b -> c) -> (a, b) -> c | ||
| + | </code> | ||
| + | |||
| + | Funcțiile primite, respectiv returnate de ''curry'' și ''uncurry'' iau tot un singur argument, numai că acesta este un tuplu. | ||
| + | |||
| + | <code> | ||
| + | *Main> let evenElements = (uncurry myFilter) even | ||
| + | |||
| + | <interactive>:12:39: | ||
| + | Couldn't match expected type `(a0 -> Bool, [a0])' | ||
| + | with actual type `a1 -> Bool' | ||
| + | In the second argument of `uncurry', namely `even' | ||
| + | In the expression: (uncurry myFilter) even | ||
| + | In an equation for `evenElements': | ||
| + | evenElements = (uncurry myFilter) even | ||
| + | *Main> let evenElements l = (uncurry myFilter) (even, l) | ||
| + | *Main> | ||
| + | </code> | ||
| + | |||
| + | </note> | ||
| ===== Funcții anonime ===== | ===== Funcții anonime ===== | ||
| - | ''TODO'' | + | |
| + | Ne propunem să scriem o funcție care primește o listă și întoarce toate elementele ei divizibile cu 5. Având deja o funcție de filtrare, putem scrie: | ||
| + | |||
| + | <code haskell> | ||
| + | testDiv5 x = x `mod` 5 == 0 | ||
| + | multiplesOf5 = myFilter testDiv5 | ||
| + | </code> | ||
| + | |||
| + | Această abordare funcționează, însă am poluat spațiul de nume cu o funcție pe care nu o folosim decât o singură dată - ''testDiv5''. | ||
| + | |||
| + | Funcțiile anonime (cunoscute și ca expresii lambda) sunt funcții fără nume, folosite des în lucrul cu funcții de ordin superior. | ||
| + | |||
| + | În Haskell, se folosește sintaxa: ''\x -%%>%% x + 5''. Funcția definită ia un parametru și returnează suma dintre acesta și 5. Caracterul ''\'' este folosit pentru că seamănă cu λ (lambda). | ||
| + | |||
| + | Rescriind funcția noastră, obținem: | ||
| + | <code haskell> | ||
| + | multiplesOf5 = myFilter (\x -> x `mod` 5 == 0) | ||
| + | </code> | ||
| + | |||
| + | Următoarele expresii sunt echivalente: | ||
| + | |||
| + | <code haskell> | ||
| + | f x y = x + y | ||
| + | f x = \y -> x + y | ||
| + | f = \x y -> x + y | ||
| + | </code> | ||
| + | |||
| + | <note> | ||
| + | Nu există vreo diferență între ''\x y -%%>%% x + y'' și ''\x -%%>%% \y -%%>%% x + y''. | ||
| + | </note> | ||
| ===== Combinatori și închideri funcționale ===== | ===== Combinatori și închideri funcționale ===== | ||
| Line 82: | Line 161: | ||
| Un **combinator** este o funcție care nu se folosește de //variabile libere//. O variabilă este liberă în definiția unei funcții dacă nu se //referă// la niciunul dintre parametrii formali ai acesteia. | Un **combinator** este o funcție care nu se folosește de //variabile libere//. O variabilă este liberă în definiția unei funcții dacă nu se //referă// la niciunul dintre parametrii formali ai acesteia. | ||
| - | Exemple de combinatori: | ||
| <code haskell> | <code haskell> | ||
| - | let f1 = \a -> a | + | -- Exemple de combinatori |
| - | let f2 = \a -> \b -> a | + | f1 = \a -> a |
| - | let f3 = \f -> \a -> \b -> f b a | + | -- prin f1 îi dăm un nume funcției anonime de după egal |
| + | -- această funcție anonimă are un parametru formal, "a" | ||
| + | -- definiția ei conține doar evaluarea lui a | ||
| + | -- este un combinator deoarece nu folosește nicio altă variabilă în afară de a | ||
| + | |||
| + | f2 = \a -> \b -> a | ||
| + | f3 = \f -> \a -> \b -> f b a | ||
| + | |||
| + | -- Exemple de "ne-combinatori" | ||
| + | f1_no = \a -> a + x | ||
| + | where x = some_other_expr | ||
| + | -- x este o variabilă liberă în contextul definiției funcției anonime de după egal | ||
| + | |||
| + | -- Pentru mai multe exemeple, continuă să citești | ||
| </code> | </code> | ||
| Line 94: | Line 185: | ||
| <code haskell> | <code haskell> | ||
| - | let flip = \f -> \a -> \b -> f b a | + | flip = \f -> \a -> \b -> f b a -- was f3 |
| </code> | </code> | ||
| Line 100: | Line 191: | ||
| <code haskell> | <code haskell> | ||
| - | let flip f = \a -> \b -> f b a | + | flip f = \a -> \b -> f b a |
| - | -- ^^^^^^^^^^^^+^^^^ | + | -- ^^^^^^^^^^^^+^^^^ |
| - | -- f este o variabilă liberă în contextul funcției anonime de după egal | + | -- f este o variabilă liberă în contextul funcției anonime de după egal |
| </code> | </code> | ||
| - | Ce ne returnează funcție flip, atunci când îi dăm un singur argument? O //închidere funcțională// **peste f**. Prin urmare, funcția **mod_flipped** de mai jos este o închidere funcțională care atunci când primește 2 parametrii va folosi funcția **mod** (stocată - într-un mod neobservabil -- în **contextul** său) și va returna restul împărțirii celui de-al doilea la primul. | + | Ce ne returnează funcția flip, atunci când îi dăm un singur argument? O //închidere funcțională// **peste f**. Prin urmare, funcția **mod_flipped** de mai jos este o închidere funcțională care atunci când primește 2 parametrii va folosi funcția **mod** (stocată - într-un mod neobservabil -- în **contextul** său) și va returna restul împărțirii celui de-al doilea la primul. |
| <code haskell> | <code haskell> | ||
| - | let mod_flipped = flip mod | + | mod_flipped = flip mod |
| </code> | </code> | ||
| Line 128: | Line 219: | ||
| ===== Exerciții ===== | ===== Exerciții ===== | ||
| - | 1. Definiți o funcție de ordin superior care primește o funcție și un număr, și aplică de două ori funcția pe numărul respectiv. | + | 1. Definiți o închidere funcțională care prefixează [1,2,3] la o listă primită ca parametru. |
| - | 2. Definiți o funcție care primește un operator binar, și întoarce același operator în care ordinea parametrilor a fost inversată //(e.g. 1/3 -> 3/1)// | + | 2. Definiți o funcție de ordin superior care primește o funcție și un număr, și aplică de două ori funcția pe numărul respectiv. |
| - | 3. Implementați și testați funcțiile: | + | 3. Definiți o funcție care primește un operator binar, și întoarce același operator în care ordinea parametrilor a fost inversată //(e.g. 1/3 -> 3/1)// |
| - | a) foldl | + | 4. Implementați și testați funcțiile: |
| - | + | - foldl | |
| - | b) foldr | + | - foldr |
| - | + | - map | |
| - | c) map | + | - filter |
| - | + | - zipWith | |
| - | d) filter | + | - compunerea de funcții (operatorul ''.'' din Haskell) |
| - | + | ||
| - | e) zipWith | + | |
| - | + | ||
| - | f) compunerea de funcții (operatorul ''.'' din Haskell) | + | |
| <note tip> | <note tip> | ||
| Line 150: | Line 237: | ||
| </note> | </note> | ||
| - | 4. Implementați, folosind foldl sau foldr: | + | 5. Implementați, folosind foldl sau foldr: |
| - | + | - map | |
| - | a) map | + | - filter |
| - | + | ||
| - | b) filter | + | |
| ===== Referințe ===== | ===== Referințe ===== | ||
| * [[https://www.haskell.org/hoogle/|Hoogle - motor de căutare pentru funcții Haskell]] | * [[https://www.haskell.org/hoogle/|Hoogle - motor de căutare pentru funcții Haskell]] | ||
laboratoare/02-functii-de-ordin-superior.1457292938.txt.gz · Last modified: 2016/03/06 21:35 by calin.cruceru
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
