====== Funcții ======

Responsabili laborator: 
  * [[mihai.dumitru@cti.pub.ro|Dumitru Mihai-Valentin]]
  * [[calin.cruceru@cti.pub.ro|Călin Cruceru]]

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ț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 decât 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 (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 =====

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 =====

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 închidere funcțională care prefixează [1,2,3] la o listă primită ca parametru.

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. 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)//

4. Implementați și testați funcțiile:
  - 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>

5. 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.