Funkcije

Pojam funkcije u Haskel jeziku ima izvesne sličnosti sa pojmom funkcije u imperativnim jezicima poput C-a ili Jave, ali izvesne razlike. Dok se u navedenim jezicima funkcija shvata kao niz instrukcija koje je potrebno izvršiti, u Haskelu funkcija predstavlja pravilnost po kojoj se od neke vrednost dobija druga vrednost. Drugim rečima u Haskelu funkcije predstavljaju transformacije vrednosti. Ovo shvatanje se podudara sa matematičkom definicijom funkcije.

Takođe, dok je u imperativnim jezicima pojam funkcije razdvojen od pojma podatka (te je teško ili nemoguće vršiti sa funkcijama ono što je moguće vršiti sa podacima), u Haskelu je granica između ova dva pojma mnogo tanja. U Haskelu, svaka funkcija je samo jedna vrednost koja je sadržana u odgovarajućem tipu. I kao što vrednosti tipa Int mogu transformisati sa odgovarajućim funkcijama, ili vrednosti tipa Bool sa logičkim operacijama i funkcijama, tako se i funkcije mogu transformisati sa odgovarajućim funkcijama...

Pojam funkcije i tip funkcije

U matematici, funkcija je pravilnost po kojoj se svakom elementu nekog skupa pridružuju elementi nekog drugog skupa. Činjenicu da neka funkcija \(f\) elementima skupa \(A\) pridružuje elemente skupa \(B\) označavamo sa \(f\colon A \to B\) i kažemo da \(f\) ima (poseduje) tip \(A \to B\). Skup \(A\) nazivamo domen a skup \(B\) kodomen funkcije \(f\)¹. Ako funkcija \(f\) elementu \(x\in A\) pridružuje vrednost \(y\in B\) to označavamo sa \(f(x) = y\).

Za funkciju tipa \(A \to B\) često kažemo da preslikava (slika, transformiše) skup \(A\) u skup \(B\). Za izraz \(f(x)\) kažemo da predstavlja primenu funkcije \(f\) na vrednost \(x\).

Dve funkcije \(f_1\) i \(f_2\) smatramo za jednake ako imaju isti domen, isti kodomen, i ako je \(f_1(x) = f_2(x)\) za svako \(x\) iz domena funkcije.

U Haskelu, analogno matematici, funkcije predstavljaju pravilnosti po kojima se vrednostima nekog tipa (domena) pridružuju vrednosti drugog tipa (kodomena). Tip funkcije koja vrednostima tipa A pridružuje vrednosti tipa B označava se sa A -> B. Tip funkcije, kao i svaki drugi tip, predstavlja kolekciju nekih vrednosti. Tip A -> B predstavlja kolekciju svih funkcija koje tip A preslikavaju tip B.

Primer 5.

Funkcija not svakoj logičkoj vrednosti dodeljuje njenu negaciju koja je takođe logička vrednost. Prema tome, funkcija not ima tip Bool -> Bool.

Primer 6.

Funkcija even, predefinisana u GHCi-ju, svakom celom broju dodeljuje logičku vrednost u zavisnosti da li je taj broj paran. Prema tome, tip funkcije even je² Int -> Bool. Isto važi i za funkciju odd koja proverava da li je broj neparan.

Za razliku od imperativnih jezika, funkcije u Haskelu uvek moraju da poseduju kodomen. Drugim rečima, primena funkcije na vrednost mora i sama da predstavlja vrednost nekog tipa. U imperativnim jezicima neretko koristimo void funkcije koje nemaju povratnu vrednost. Takve funkcije se ne koriste u Haskelu.

Zadatak 1. Neka je \(B\) skup koji sadrži dve vrednosti. Koliko postoji funkcija tipa \(B \to B\)? Koje su to funkcije?

Zadatak 2. Neka je \(U\) skup koji sadrži jednu vrednost. Koliko postoji funkcija tipa \(\mathbb N \to U\)? Koliko postoji funkcija tipa \(U \to \mathbb N\)?

Lambda izrazi

Haskel je zasnovan na matematičkom formalizmu zvanom lambda račun. Lambda račun je formalni sistem koji opisuje pojam izračunljivosti pomoću definicija i primene funkcija. Ovde neće biti prezentovan lambda račun, ali mnoge stvari koje slede važe i za sam lambda račun.

U Haskelu, funkcije su vrednosti koje se definišu pravilom apstrakcije³. U Haskelu sintaksa za apstrakciju je \x -> v. Lambda apstrakcija se sastoji od znaka⁴ \, zatim imena parametra (u ovom primeru to je x ali može biti bilo koja validna labela), zatim strelice -> nakon koje sledi povratna vrednost funkcije odnosno neki izraz koji potencijalno zavisi od parametra (tj. od x). Izraz \x -> v nazivamo lambda funkcija a izraz koji sledi nakon strelice (tj. v), nazivamo telo lambda funkcije.

g = (\x -> (2 * x))

ghci> g 10
20

Svaki izraz oblika m n, gde su m i n neki izrazi, nazivamo aplikacija⁷. U Haskelu, svaka aplikacija predstavlja pokušaj primene izraza m na izraz n. Međutim, m n nema smisla ako m nije funkcija. Na primer, "primena" 'a' 'b' daje grešku

ghci> 'a' 'b'
<interactive>:15:1: error:
    • Couldn't match expected type ‘Char -> t’ with actual type ‘Char’
    • The function ‘'a'’ is applied to one value argument,
        but its type ‘Char’ has none
      In the expression: 'a' 'b'
      In an equation for ‘it’: it = 'a' 'b'
    • Relevant bindings include it :: t (bound at <interactive>:15:1)

U prethodnom primeru, kada smo u GHCi prompt uneli g 10 i pritisnuli Enter, GHCi je zamenio ime g sa odgovarajućim lambda izrazom. Tom zamenom se dobija izraz (\x -> (2 * x)) 10. Štaviše, i sami smo mogli da unesemo izraz u prompt i dobili bismo isti rezultat:

ghci> (\x -> (2 * x)) 10
20

Izraz oblika (\x -> a) b, gde su a i b proizvoljni lambda izrazi, naziva se redeks. Redeksi zapravo predstavljaju smislene primene funkcije na vrednost.

Primer redeksa je upravo (\x -> (2 * x)) 10 ali i g 10 jer je g po definiciji (\x -> (2 * x)). Za razliku od izraza 'a' 'b', svaki redeks predstavlja smislenu aplikaciju funkcije na vrednost.

površinaKruga = (\r -> (2 * r^2))

ghci> površinaKruga 2
12.566370614359172
ghci> površinaKruga 5
78.53981633974483

Zadatak 4. Temperatura od \(x\) stepeni Farenhajta je jednaka temperaturi od \(\frac{5}{9}(x - 32)\) stepeni Celzijusa. Napisati funkciju uCelzijuse koja stepene Farenhajta pretvara u stepne Celzijusa. Izraziti i stepene Farenhajta preko stepena Celzijusa, i napisati funkciju uFarenhajte koja vrši konverziju. Potvrditi sa obe funkcije da je \(30^\circ \mathrm C\) jednako \(86^\circ \mathrm F\)

Beta redukcija

Ako je data matematička funkcija \(f(x)=2*x\), tada se postupak nalaženja vrednosti \(f(10)\) sastoji u tome da se svako pojavljivanje promenljive \(x\) u izrazu \(2*x\) zameni sa argumentom \(10\). Time se dobija izraz \(2*10\) koji može direktno da se izračuna. Analognim postupkom redeksi se mogu svesti na neku vrednost koja u sebi ne sadrži redeks.

Opisani postupak nazivamo beta redukcija. Tačnije beta redukcija je zamena redeksa (\x -> a) b sa izrazom koji se dobije kada se izrazu a sva pojavljivanja imena x zamene sa izrazom b. Pritom se početak lambda izraza, \x ->, uklanja.

Postavlja se pitanje, da li je poredak evaluacije redeksa važan? Da li bismo isti rezultat dobili i da smo prvo izvršili beta redukciju unutrašnjeg redeksa a zatim i spoljašnjeg?

Osobina da poredak vršenja beta redukcije ne utiče na krajnu vrednost je poznata kao konfluentnost. Neće za svaki izraz važiti konfluentnost, a i u slučajevima kada važi, različit poredak beta redukcije može zahtevat drastično različit broj koraka (pa samim tim i vremena potrebnog kompletnu beta redukciju). Više o tome ćemo reći kasnije...

Tip funkcije

Do sada smo smo objasnili kako se definišu funkcije, ali nismo naveli mnogo o tipu funkcije. Razlog tome je što je Haskel automatski zaključivao tip definisanih funkcija. Ipak, kao i sa drugim vrednostima, programer može (i poželjno je) da eksplicitno navede tip funkcije.

g :: Int -> Int
g = (\x -> (2 * x))

h :: [Int] -> Int
h = (\x -> (head x + 1))

Zanimljivo je primetiti šta se dešava sa tipom funkcije kada se funkcija primeni na vrednost. Pre svega, Haskel će proveriti da li se tip te vrednosti i domen funkcije podudaraju. Ako to nije slučaj, tada će doći do tipske greške.

ghci> h 2
<interactive>:3:3: error:
    • No instance for (Num [Int]) arising from the literal ‘2’
    • In the first argument of ‘h’, namely ‘2’
      In the expression: h 2
      In an equation for ‘it’: it = h 2

Ako nije došlo do tipske greške, tada primena funkcija na neku vrednost predstavlja dobro tipiziran izraz. Pritom, ako je funkcija f tipa A -> B, a vrednost v tipa A, tada je f v predstavlja vrednost tipa B. Beta redukcijom moguće je odrediti tačnu vrednost izraza f v, ali i bez redukcije znamo da ta vrednost poseduje tip B. Prosto rečeno, primenom funkcije tipa A -> B na vrednosti tipa A "brišemo" A -> iz tipa⁸.

Zadatak 5. Deklarisati tipove funkcija iz prethodnih zadataka ove lekcije.

Funkcije više promenljivih

Do sada je prikazano kako se mogu definisati funkcije samo sa jednim parametrom, ali su u prethodnoj lekciji korišćene funkcije sa dva parametara (kao što je funkcija mod koja određuje ostatak pri deljenju ili funkcija elem koja ispituje da li se element nalazi u listi). Postavlja se pitanje kako se ovakve funkcije definišu?

Pažljivi čitalac koji se seća sadržaja prethodne lekcije mogao je sam da konstruiše funkcije sa dva parametara. Naime, u prethodnoj sekciji smo videli kako se uređeni parovi mogu konstruisati. Prema tome, ako želimo funkciji da prosledimo dve vrednosti, dovoljno je da napišemo funkciju koja uzima jedan uređen par⁹.

ljubav :: (String, String) -> String
ljubav = (\x -> (fst x ++ " voli " ++ snd x ++ "!"))

ghci> ljubav ("Ana", "Milovana")
"Ana voli Milovana!"
ghci> ljubav ("Marijana", "Marijana")
"Marijana voli Marijana!"

Zadatak 6. Napisati funkciju zapreminaValjka :: (Double, Double) -> Double koja na osnovu uređenog para visine i poluprečnika baze računa zapreminu valjka.

Pozivanje ovako definisane funkcije podseća na pozivanje funkcija u imperativnim jezicima. Ali primetimo da smo mi u prethodnoj lekciji funkcije poput mod pozivali sa mod 7 3 a ne sa mod (7, 3). Takođe možemo da primetimo da iako funkciji prosleđujemo dva podatka, funkcija ljubav suštinski uzima samo jednu vrednost tipa (String, String).

Lambda račun, koji je osmišljen pola veka pre Haskela, je zamišljen kao minimalan formalni sistem i kao takav takav ne poseduje pojam uređene n-torke. Umesto toga, funkcije sa više parametara u lambda računu se realizuju uz pomoć 'trika'. Naime, da bi dobili funkciju od više parametara, definisaćemo funkciju f od jednog parametra čija povratna vrednost je druga funkcija. Na taj način, izraz (f x) predstavlja novu funkciju koju možemo da primenimo na neku drugu vrednost. Ako je rezultat i ove primene funkcija, tada taj rezultat možemo da primenimo na sledeću vrednost i tako dalje.

ghci> (aritm 8) 10
9

Ipak, aplikacija (aritm 8) 10 ne izgleda baš u potpunosti isto kao aplikacija mod 7 2 koju smo videli u prethodnoj lekciji. Razlog tome je što u Haskelu aplikacija (primena funkcije na argument) je levo asocijativna operacija što znači da se izraz (f x) y može jednostavnije zapisati kao f x y. I zaista, ako se vratimo na prethodni primer, možemo se uveriti u to:

ghci> aritm 8 10
9
ghci> aritm 20 100
60

Kog tipa je funkcija aritm? Za trenutak pretpostavimo da su parametri x i y tipa Double¹⁰. Funkcija aritm uzima vrednost tipa Double i vraća neku funkciju, nazovimo je g. Funkcija g uzima i vraća vrednost tipa Double te je njen tip Double -> Double. Sada možemo da zaključimo da funkcija aritm poseduje tip Double -> (Double -> Double) jer uzima vrednost tipa Double i vraća vrednost tipa Double -> Double.

Koristeći opisan postupak, možemo konstruisati funkcije koje poseduju tri ili više parametara¹¹. Tom prilikom konstruišemo funkcije tipa T₁ -> (T₂ -> ( … -> (Tₙ -> B))) gde tipovi T₁, ..., Tₙ predstavljaju tipove parametara funkcije, a B povratnu vrednost takve funkcije. Primenom funkcije f tipa T₁ -> (T₂ -> ( … -> (Tₙ -> B))) na vrednost tipa T₁ dobija se funkcija tipa T₂ -> (T₃ -> … -> (Tₙ -> B)). Novodobijena funkcija može se primeniti na vrednost tipa T₂ čime se dobija funkcija tipa T₃ -> … -> (Tₙ -> B). Postupak se može ponavljati sve dok se ne stigne do vrednosti tipa B.

Funkcija koja "uzima" ili "vraća" neku drugu funkciju naziva se funkcija višeg reda. Mnogi programski jezici nemaju podršku za funkcije višeg reda, ali kao što vidimo, u Haskelu je ovaj pojam je sasvim prirodan.

zapremina :: Double -> (Double -> (Double -> Double))
zapremina = (\a -> (\b -> (\c -> (a * b * c))))

Zadatak 8. Napisati funkciju zapreminaValjka :: Double -> (Double -> Double) koja na osnovu prosleđene visine i poluprečnika baze računa zapreminu valjka.

Prelude

Prelid¹² je kratka muzička forma improvizacijskog karaktera, koja se koristi kao uvod u veća muzička dela. U Haskelu, Prelude predstavlja kôd koji je dostupan svakom programu. Definicije iz Prelida, mogu se shvatiti kao uvod u definicije koje je korisnik napisao.

Sve predefinisane funkcije koje smo do sada predstavili, poput not, mod, div, length, head, fst, i tako dalje, zapravo su definisane u Haskel Prelidu. Takođe, konstante poput pi su definisane u Prelidu. U narednim lekcijama videćemo kako su tačno navedene funkcija definisane, i upoznaćemo još mnoge druge definicije iz Prelida.

Zadaci

Zadatak 9. Rešenja \(x_1\) i \(x_2\) kvadratne jednačine \(ax^2+bx+c=0\) su data sa kvadratnom formulom \[x_{1,2} = \frac{-b\pm\sqrt{b^2-4ac}}{2a}.\] Implementirati funkciju rešenja :: Double -> (Double -> (Double -> (Double, Double))) koja za tri prosleđena argumenta \(a\), \(b\) i \(c\) vraća uređeni par rešenja koja su dobijena putem navedene formule. Pretpostaviti da su koeficijenti tako zadati da su sve računske operacije definisane (u realnom domenu).

primeni :: (Int -> Bool) -> ((Int, Int) -> (Bool, Bool))
primeni = (\f -> (\par -> (f (fst par), f (snd par))))

ghci> primeni paran (2, 7)
(True,False)

Za naredne zadatke neophodno je podsetiti se funkcija za rad sa listama iz prethodne lekcije: length, head, last, init, tail, reverse, elem.

inicijali :: [Char] -> ([Char] -> [Char])
inicijali = (\x1 -> (\x2 -> (
    let y1 = head x1; y2 = head x2
    in [x1] ++ "." ++ [x2] ++ "."
  )))

ukloni3 :: [Char] -> [Char]
ukloni3 = (\x -> (tail (tail (tail x))))

palindrom :: [Char] -> Bool
palindrom = (\s -> (s == reverse s))

zbir :: (Double, Double) -> ((Double, Double) -> (Double, Double))
zbir = (\u -> (\v -> (fst u + fst v, snd u + snd v)))