Differences

This shows you the differences between two versions of the page.

--- laboratoare:02-functii-de-ordin-superior [2016/03/06 21:35]
calin.cruceru [Funcții anonime]
+++ laboratoare:02-functii-de-ordin-superior [2016/03/06 23:34] (current)
mihai.dumitru2201
@@ Line 1: / Line 1: @@
 ====== 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 =====
@@ 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ă
   * toate elementele pare
-  * toate elementele mai mari ca 10
+  * toate elementele mai mari decât 10
 <code haskell>
@@ Line 66: / Line 68: @@
 </code>
-===== Combinatori și închideri funcționale =====
-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.
+===== Currying vs. uncurrying =====
-Exemple de combinatori:
+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.
-<code haskell>
-let f1 = \a -> a
-let f2 = \a -> \b -> a
-let f3 = \f -> \a -> \b -> f b a
-</code>
-Închiderile funcționale (**closures**) sunt opusul combinatorilor - se folosesc de variabile libere în definiția lor.  Cu alte cuvinte, sunt funcții care, pe lângă definiție, conțin și un **environment** de care se folosesc; acest environment conține variabilele libere despre care vorbeam.  Denumirea provine din faptul că environment-ul nu este menționat explicit, el este determinat implicit; spunem că funcția **se închide** peste variabilele (//libere//) **a**, **b**, etc.
+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''.
-Diferența dintre combinatori și închideri funcționale este de multe ori subtilă.  Să aruncăm o privire asupra unuia dintre exemplele de mai sus.
+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 haskell>
+<code>
-let flip = \f -> \a -> \b -> f b a
+*Main> :t myFilter
+myFilter :: (a -> Bool) -> [a] -> [a]
 </code>
-După cum am spus, acesta este un combinator.  Ținând cont de faptul că în Haskell **currying**-ul funcțiilor (gândiți-vă la //parantezarea tipului//) nu contează, putem rescrie această funcție astfel:
+Ș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//.
-<code haskell>
+Tipul funcției noastre trebuie interpretat astfel:\\
-let flip f = \a -> \b -> f b a
+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).
-          -- ^^^^^^^^^^^^+^^^^
-          --     f este o variabilă liberă în contextul funcției anonime de după egal
+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>
-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.
+Funcțiile primite, respectiv returnate de ''curry'' și ''uncurry'' iau tot un singur argument, numai că acesta este un tuplu.
-<code haskell>
+<code>
-let mod_flipped = flip mod
+*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>
-Alte exemple de închideri funcționale:
+</note>
+===== Funcții anonime =====
+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>
-mod3 x = mod x 3 -- închidere funcțională peste funcția mod din Prelude și constanta 3
+testDiv5 x = x `mod` 5 == 0
-plus5 x = x + 5  -- închidere funcțională peste funcția (+) și constanta 5
+multiplesOf5 = myFilter testDiv5
-(+5)             -- aceeași ca mai sus;
-                 --     (+) este o funcție care primește 2 argumente și se evaluează la suma lor
-                 --     (+5) este închiderea funcțională rezultată în urma "hardcodării" unuia dintre argumente
 </code>
-Mai multe detalii teoretice despre închideri funcționale, variabile legate/nelegate și combinatori se vor discuta în cadrul cursului.
+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''.
-<note tip>
+Funcțiile anonime (cunoscute și ca expresii lambda) sunt funcții fără nume, folosite des în lucrul cu funcții de ordin superior.
-Puteți găsi și alte exemple de închideri funcționale care se găsesc în acest suport de laborator?
-</note>
-===== 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.
+Î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).
-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''.
+Rescriind funcția noastră, obținem:
+<code haskell>
+multiplesOf5 = myFilter (\x -> x `mod` 5 == 0)
+</code>
-Operația inversă se numește "uncurry": ''f : X → Y → Z,   uncurry(f): X × Y → Z''.
+Următoarele expresii sunt echivalente:
-===== Funcții anonime =====
+<code haskell>
-''TODO''
+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 =====
@@ Line 129: / 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.
-Exemple de combinatori:
 <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>
@@ Line 141: / Line 185: @@
 <code haskell>
-let flip = \f -> \a -> \b -> f b a
+flip = \f -> \a -> \b -> f b a -- was f3
 </code>
@@ Line 147: / Line 191: @@
 <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>
-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>
-let mod_flipped = flip mod
+mod_flipped = flip mod
 </code>
@@ Line 175: / Line 219: @@
 ===== Exerciții =====
-. 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.
+. Definiți o închidere funcțională care prefixează [1,2,3] la o listă primită ca parametru.
-. 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)//
+. 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.
-. Implementați și testați funcțiile:
+. 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
+. 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>
@@ Line 197: / Line 237: @@
 </note>
 . Implementați, folosind foldl sau foldr:
+  - map
-a) map
+  - filter
-b) filter
 ===== Referințe =====
   * [[https://www.haskell.org/hoogle/|Hoogle - motor de căutare pentru funcții Haskell]]

pp-cb

User Tools

Site Tools

Differences

Page Tools