Differences

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

--- laboratoare:02-functii-de-ordin-superior [2016/03/06 15:38]
mihai.dumitru2201 [Funcții de ordin superior]
+++ 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 65: / Line 67: @@
 greaterThan10 = myFilter (> 10)
 </code>
-===== Închideri funcționale =====
-''TODO''
 ===== Currying vs. uncurrying =====
-''TODO''
+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''.
+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 =====
-''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:
-===== Exerciții =====
+<code haskell>
+testDiv5 x = x `mod` 5 == 0
+multiplesOf5 = myFilter testDiv5
+</code>
-. 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.
+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''.
-. 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)//
+Funcțiile anonime (cunoscute și ca expresii lambda) sunt funcții fără nume, folosite des în lucrul cu funcții de ordin superior.
-. Implementați și testați funcțiile:
+Î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).
-a) foldl
+Rescriind funcția noastră, obținem:
+<code haskell>
+multiplesOf5 = myFilter (\x -> x `mod` 5 == 0)
+</code>
-b) foldr
+Următoarele expresii sunt echivalente:
-c) map
+<code haskell>
+f x y = x + y
+f x = \y -> x + y
+f = \x y -> x + y
+</code>
-d) filter
+<note>
+Nu există vreo diferență între ''\x y -%%>%% x + y'' și ''\x -%%>%% \y -%%>%% x + y''.
+</note>
-e) zipWith
+===== Combinatori și închideri funcționale =====
-f) compunerea de funcții (operatorul ''.'' din Haskell)
+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.
+<code haskell>
+-- Exemple de combinatori
+f1 = \a -> 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>
+Î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.
+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.
+<code haskell>
+flip = \f -> \a -> \b -> f b a -- was f3
+</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:
+<code haskell>
+flip f = \a -> \b -> f b a
+      -- ^^^^^^^^^^^^+^^^^
+      --     f este o variabilă liberă în contextul funcției anonime de după egal
+</code>
+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>
+mod_flipped = flip mod
+</code>
+Alte exemple de închideri funcționale:
+<code haskell>
+mod3 x = mod x 3 -- închidere funcțională peste funcția mod din Prelude și constanta 3
+plus5 x = x + 5  -- închidere funcțională peste funcția (+) și constanta 5
+(+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.
 <note tip>
-Dacă nu cunoașteți vreuna dintre funcții, o puteți căuta pe Hoogle pentru a vedea tipul și scopul ei.
+Puteți găsi și alte exemple de închideri funcționale care se găsesc în acest suport de laborator?
 </note>
+===== Exerciții =====
-. Implementați, folosind foldl sau foldr:
+. Definiți o închidere funcțională care prefixează [1,2,3] la o listă primită ca parametru.
-a) map
+. 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.
-b) filter
+. 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)//
-===== Referințe =====
+. Implementați și testați funcțiile:
-''TODO''
+  - foldl
+  - foldr
+  - map
+  - filter
+  - zipWith
+  - compunerea de funcții (operatorul ''.'' din Haskell)
+<note tip>
+Dacă nu cunoașteți vreuna dintre funcții, o puteți căuta pe Hoogle pentru a vedea tipul și scopul ei.
+</note>
+. Implementați, folosind foldl sau foldr:
+  - map
+  - filter
+===== Referințe =====
+  * [[https://www.haskell.org/hoogle/|Hoogle - motor de căutare pentru funcții Haskell]]
+  * [[https://wiki.haskell.org/Higher_order_function|Higher order functions]]
 ===== Soluții laborator =====
   - [[https://github.com/Programming-Paradigms/Labs/archive/master.zip | Solutii lab 2]]
   - Puteti, alternativ, sa folositi urmatorul repository git [[https://github.com/Programming-Paradigms/Labs]] pentru a descarca solutiile si le sincroniza, ulterior.

pp-cb

User Tools

Site Tools

Differences

Page Tools