Responsabili laborator:

• Dumitru Mihai-Valentin
• 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ț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

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

myFunction x
        | x < 10    = "One digit"
        | x < 100   = "Two digits"
        | x < 1000  = "Three digits"
        | otherwise = "More than four digits"

Testăm funcțiile scrise:

*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]

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:

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

Acum putem rescrie funcțiile noastre, într-un mod mai elegant, utilizând funcția de filtrare:

evenElements = myFilter even
 
greaterThan10 = myFilter (> 10)

Currying (numit după 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?

*Main> :t myFilter
myFilter :: (a -> Bool) -> [a] -> [a]

Și în laboratorul trecut, am observat că nu există o separare între domeniu și codomeniu, de genul
(a -> Bool) x [a] -> [a].

*Main> :t curry
curry :: ((a, b) -> c) -> a -> b -> c
*Main> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c

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

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:

testDiv5 x = x `mod` 5 == 0
multiplesOf5 = myFilter testDiv5

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:

multiplesOf5 = myFilter (\x -> x `mod` 5 == 0)

Următoarele expresii sunt echivalente:

f x y = x + y
f x = \y -> x + y
f = \x y -> x + y

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

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

flip = \f -> \a -> \b -> f b a -- was f3

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:

flip f = \a -> \b -> f b a
      -- ^^^^^^^^^^^^+^^^^ 
      --     f este o variabilă liberă în contextul funcției anonime de după egal

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.

mod_flipped = flip mod

Alte exemple de închideri funcționale:

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

Mai multe detalii teoretice despre închideri funcționale, variabile legate/nelegate și combinatori se vor discuta în cadrul cursului.

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:

1. foldl
2. foldr
3. map
4. filter
5. zipWith
6. compunerea de funcții (operatorul . din Haskell)

5. Implementați, folosind foldl sau foldr:

1. map
2. filter

• Hoogle - motor de căutare pentru funcții Haskell
• Higher order functions

1. Solutii lab 2
2. Puteti, alternativ, sa folositi urmatorul repository git https://github.com/Programming-Paradigms/Labs pentru a descarca solutiile si le sincroniza, ulterior.