pp-cb

This is an old revision of the document!

---

====== Funcții ====== * Semnificatia termenului //aplicatie// * Definirea **functiilor anonime** in Haskell: <code haskell> \x1 x2 ... -> expr </code> * 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 ===== Funcții de ordin superior ===== Funcțiile de ordin superior sunt funcții care lucrează cu alte funcții: le primesc ca parametrii sau le returnează. 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 <code haskell> evenElements [] = [] evenElements (x:xs) = if even x then x : evenElements xs else evenElements xs greaterThan10 [] = [] greaterThan10 (x:xs) = if x > 10 then x : greaterThan10 xs else greaterThan10 xs </code> <note> În loc de ''if'', puteți folosi următoarea sintaxă: <code haskell> myFunction x | x < 10 = "One digit" | x < 100 = "Two digits" | x < 1000 = "Three digits" | otherwise = "More than four digits" </code> </note> Testăm funcțiile scrise: <code> *Main> evenElements [1..20] [2,4,6,8,10,12,14,16,18,20] *Main> greaterThan10 [1..20] [10,11,12,13,14,15,16,17,18,19,20] </code> Observăm că funcțiile definite mai sus sunt foarte asemănătoare. De fapt, doar condiția verificată în ''if'' diferă. Scriem, deci, o funcție generală care primește o funcție pentru testarea elementelor: <code haskell> -- In primul pattern, nu folosim functia de testare, deci nu ne intereseaza ca aceasta -- sa fie legata la un nume, lucru marcat prin "_" myFilter _ [] = [] myFilter test (x:xs) = if test x then x : myFilter test xs else myFilter test xs </code> Acum putem rescrie funcțiile noastre, într-un mod mai elegant, utilizând funcția de filtrare: <code haskell> evenElements = myFilter even greaterThan10 = myFilter (> 10) </code> ===== 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. 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''. ===== Funcții anonime ===== ''TODO'' ===== 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. <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> Puteți găsi și alte exemple de închideri funcționale care se găsesc în acest suport de laborator? </note> ===== 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. 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)// 3. Implementați și testați funcțiile: a) foldl b) foldr c) map d) filter e) zipWith f) 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> 4. Implementați, folosind foldl sau foldr: a) map b) 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.