Sintaksa u funkcijama

Brisanje zagrada

U prethodnim primerima videli smo da lambda izrazi mogu biti veoma nepregledni zbog višestrukih zagrada. Zbog toga su u lambda račun, pa i Haskel, uvedene konvencije koje omogućavaju brisanje suvišnih zagrada u lambda izrazima:

Zagrade oko lambda izraza ne zapisujemo. Kada unosimo neki izraz u GHCi, tada nije neophodno da postavljamo zagradu koja obuhvata celokupan izraz. Isto važi i kada u kodu definišemo neki lambda izraz. Na primer, umesto s = (f 20) pišemo f = f 20.
Aplikacija ima veći prioritet u odnosu na apstrakciju. Praktično to znači da telo lambda funkcije nije neophodno postavljati u posebne zagrade. Na primer umesto \x -> (f x) pišemo \x -> f x.
Aplikacija lambda izraza je levoasocijativna. To znači da se izraz oblika ((M N) P) može zapisati kao M N P. Induktivnim argumentom sledi da se i izraz (((M N) P) Q) može zapisati kao M N P Q, itd... Na primer, umesto (zbir 22) 33 pišemo samo zbir 22 33. Sa druge strane, iz izraza f 10 (g 20) ne možemo obrisati zagrade, jer bismo time dobili izraz koji se interpretira kao ((f 10) g) 20.
Apstrakcija je desnoasocijativna. Npr. umesto \x -> (\y -> x + y) pišemo \x -> \y -> x + y.
Višestruke apstrakcije se mogu svesti pod jednu lambdu. Na primer umesto \x -> \y -> x + y pišemo samo \x y -> x + y. Obratite pažnju da parametri funkcije moraju međusobno biti razdvojeni razmakom.

Primer 1.

Pojednostavimo lambda izraz (\x -> (\y -> ((f x) (g y)))).

Pre svega, zagrade oko celog lambda izraza mogu se obrisati, čime se dobija \x -> (\y -> ((f x) (g y))). Višestruka apstrakcija može se svesti pod jednu apstrakciju, čime se dobija \x y -> ((f x) (g y)). Zagrade u telu lambda funkcije nisu neophodne, jer se u tim zagradama nalazi jedna aplikacija (a po drugom pravilu, aplikacija ima veći prioritet u odnosu na apstrakciju) \x y -> (f x) (g y). Kako je aplikacija levo asocijativna, levi par zagrada se može obrisati \x y -> f x (g y)

Osim pravila o zagradama u lambda izrazima, koristi se i jedno pravilo koje se odnosi na zagrade u tipovima. Ovo pravilo kaže da je -> desno-asocijativan operator, odnosno da a -> (b -> c) može pisati kao a -> b -> c.

Primer 2.

Pogledajmo tipove Int -> (Char -> Bool) i (Int -> Char) -> Bool. Gledano kao na nizove simbola, razlika između ova dva tipa je samo raspored zagrada. Ali tipovi nam govore mnogo o ovim funkcijama!

Neka je f :: Int -> (Char -> Bool). Tada primenom f na neku vrednost n :: Int dobijamo funkciju f n :: Char -> Bool. Funkciju f n možemo zatim da primenimo vrednost b :: Bool, i dobijemo vrednost tipa Char. Dakle, f možemo da shvatimo kao binarnu funkciju koja uzima jednu Int i jednu Char vrednost. Tip ove funkije, po gorepomenutom pravilu, možemo da napišemo i kao Int -> Char -> Bool

Neka je g :: (Int -> Char) -> Bool. Funkciju g možemo da primenimo samo na neku drugu funkciju h :: Int -> Char i time dobijemo vrednost tipa Char. Dakle g je funkcija "jednog argumenta"¹.

1. Svaka funkcija u Haskelu je funkcija jednog argumenta. Ali zbog karijevanja, funkcije čiji tip je oblika a1 -> (a2 -> b) možemo da nazivamo funkcijama dva argumenta, itd...

Primer 3.

U prethodnij lekciji, u zadatku 7 se tražilo da se napiše funkcija primeni :: (Int -> Bool) -> ((Int, Int) -> (Bool, Bool)) koja uzima jednu funkciju f :: Int -> Bool, jedan uređen par tipa (Int, Int) i vraća uređen par koji se dobija primenom f na svaku koordinatu uređenog para. Rešenje do kog smo došli je

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

Navedena lambda je oblika (\f -> (\par -> ...)). Pre svega, možemo se osloboditi zagrada oko celog izraza, a zatim svesti dvostruku apstrakciju pod jednu lambdu.

Tip funkcije je oblika a -> (b -> c), pa možemo ukloniti jedan par zagrada.

Dobijeni kod je nešto čitljiviji:

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

Iz ovog koda ne možemo ukloniti više zagrada

Zadatak 1. Uraditi ponovo zadatke iz prethodne lekcije korsteći što manje zagrada u kodu.

If then else

Jedna od osnovnih mogućnosti koju svaki programski jezik mora posedovati je sposobnost promene toka izvršavanja programa u zavisnosti od stanja u kom se nalazi. Ovakvu promenu toka nazivamo grananje.

Izraz if then else je najjednostavniji primer grananja u Haskelu². Sintaksa za ovu konstrukciju ima oblik if t then a else b, gde je t neki logički izraz kog nazivamo uslov, a a i b izrazi istog tipa. Izraz if t then a else b se evaluira u a ako se t evaluira u True, a u suprotnom u b. Sledeći primer ilustruje korišćenje if then else konstrukcije:

2. Izraz u potpunosti odgovara trenarnom operatoru ? : koji je prisutan u mnogim imperativnim jezicima.

ghci> if 5 > 0 then "5 je pozitivan broj" else "5 nije pozitivan broj"
"5 je pozitivan broj"

U prikazanom primeru, uslov je konstantan, te će navedeni if then else izraz uvek imati istu vrednost. Mnogo korisnije je kada if then else postavimo u telo funkcije:

daLiJepozitivan = \x -> if x > 0 then show x ++ "jeste" else show x ++ "nije"

ghci> daLiJepozitivan 3
"jeste"

Važno je da poštujemo tri pravila:

Uslov (izraz između if i then klauze) mora biti tipa Bool.
Moraju se navesti povratne vrednosti za oba slučaja (u suprotnom izraz bi mogao biti nedefinisan u zavisnosti od vrednosti uslova).
Povratne vrednosti za oba slučaja moraju biti istog tipa (u suprotnom izraz bi imao različit tip u zavisnosti od vrednosti uslova).

Zadatak 2. Bez korišćenja ugrađene funkcije max, implementirati funkciju max' :: Int -> Int -> Int koja nalazi maksimum dva broja.

max' :: Int -> Int -> Int
max' = \x y -> if x > y then x else y

Guards

Guards je naziv za sintaksu koja omogućava testiranje više uslova. Svaki od uslova je logički izraz koji se navodi nakon vertikalne crte |, a nakon uslova potrebno je staviti i (povratnu) vrednost funkcije.

Guards sintaksa može se koristiti samo pri definisanju funkcije (za razliku of if then else sintakse, guards ne predstavlja izraz). Opšti oblik guards sintakse bi bio³:

f x1 x2 x3 
  | uslov1 = vrednost1
  | uslov2 = vrednost2
  ...
  | uslovN = vrednostN

U ovom zapisu, f je ime funkcije koja se definiše, a x1, x2, x3 su parametri funkcije f. Uslovi, uslov1 ... uslovN su izrazi koji se evaluiraju u logičku vrednost.

Kao i kod if then else konstrukcije, i kod guards konstrukcije sve povratne vrednosti moraju biti istog tipa.

Primer 4.

Funkcija pozitivan :: Int -> [Char] koja vraća nisku "Pozitivan" ako je broj veći ili jednak nuli, a u suprotnom "Negativan", može se ovako definisati

pozitivan :: :: Int -> [Char]
pozitivan x
 | x >= 0 = "Pozitivan"
 | x < 0 = "Negativan"

Prilikom "poziva" pozitivan (-4), prvo će se proveriti prvi navedeni slučaj, odnosno x >= 0. Kako se -4 >= 0 beta redukuje u False, proveriće se naredni slučaj x < 0. Kako se -4 < 0 redukuje u True, vrednost pozitivan (-4) je "Negativan".

Dakle, sa guards sintaksom moguće je proveriti niz uslova. Funkcija će imati vrednost koja odgovara prvom tačnom uslovu. Ako ni jedan od uslova nije tačan, tada će doći do izuzetka.

pozitivan' :: :: Int -> [Char]
pozitivan' x
 | x > 0 = "Pozitivan"
 | x < 0 = "Negativan"

U ovoj, lošoj, definiciji uslov x == 0 nikad nije proveren, zbog čega će poziv pozitivan' 0 dovesti do izuzetka.

Primer 5.

Pogledajmo nešto složeniji primer. Funkcija koja vraća opis jačine zemljotresa na osnovu njegove jačine u Rihterima može biti definisana sa narednim kodom:

opisZemljotresa :: Double -> [Char]
opisZemljotresa r
  | (r >= 0.0) && (r < 2.0) = "Mikro"
  | (r >= 2.0) && (r < 4.0) = "Manji"
  | (r >= 4.0) && (r < 5.0) = "Lakši"
  | (r >= 5.0) && (r < 6.0) = "Srednji"
  | (r >= 6.0) && (r < 7.0) = "Jak"
  | (r >= 7.0) && (r < 8.0) = "Velik"
  | (r >= 8.0) && (r < 10.0) = "Razarajući"
  | r >= 10 = "Epski"

Ako pozovemo opisZemljotresa 5.6, tada će uslov (r >= 5.0) && (r < 6.0) biti zadovoljen zbog čega će se opisZemljotresa 5.6 evaluirati "Srednji". Ova funkcija nije totalna, jer nijedan slučaj ne odgovara negativnoj vrednosti r.

U prethodnom primeru možemo primetiti da uslove možemo pojednostaviti. Naime kako su uslovi poređani redom po jačini zemljotresa, možemo se osloboditi dela uslova kojim se proverava da je jačina zemljotresa jača od nekog intenziteta⁴. Stoga funkciju opisZemljotresa možemo i ovako definisati

opisZemljotresa :: Double -> [Char]
opisZemljotresa r
  | r < 0.0 = "Greška"
  | r < 4.0 = "Mikro"
  | r < 4.0 = "Manji"
  | r < 5.0 = "Lakši"
  | r < 6.0 = "Srednji"
  | r < 7.0 = "Jak"
  | r < 8.0 = "Velik"
  | r < 10.0 = "Razarajući"
  | r >= 10 = "Epski"

Pozivanjem opisZemljotresa 5.6 ponovo dobijamo "Srednji". Iako su i uslovi r < 7.0, r < 8.0, r < 10.0 tačni, uslov r < 6.0 je prvi naveden. Dodaat je i uslov koji u slučaju negativnog argumenta vraća nisku "Greška".

Primetimo da je i u ovom (kao i u prethodnom primeru) na poslednjem mestu postavljen slučaj koji je zadovoljen kada svi ostali slučajevi nisu⁵. Zbog toga, za poslednji uslov ne mora se stavljati nikakav izraz, već je dovoljno postaviti konstantu True, i tada će poslednji uslov "uhvatiti" sve što nije uhvaćeno sa prethodnim uslovima. Uobičajeno je da se na kraju guards-a postavi konstanta otherwise koja je ime za vrednost True⁶:

6. Zaista, u GHCi-u proverite da je otherwise == True.

opisZemljotresa r
  | r < 0.0 = "Greška"
  | r < 4.0 = "Mikro"
  | r < 4.0 = "Manji"
  | r < 5.0 = "Lakši"
  | r < 6.0 = "Srednji"
  | r < 7.0 = "Jak"
  | r < 8.0 = "Velik"
  | r < 10.0 = "Razarajući"
  | otherwise = "Epski"

Zadatak 3. Definisati funkciju max3 :: Int -> Int -> Int -> Int sa guards sintaksom, koja vraća najveću od tri celobrojne vrednosti.

Jedno od mogućih rešenja bi bilo:

max3 :: Int -> Int -> Int -> Int
max3 x y z
  | x <= z && y <= z = z
  | x <= y && z <= y = y
  | otherwise        = x

Podudaranje oblika

Podudaranje oblika⁷ je sintaksa koja dozvoljava da se vrednosti funkcije definišu u zavisnosti od "oblika" argumenta. Da bismo definisali funkciju pomoću podudaranja oblika, potrebno je da odmah nakon imena funkcije navedemo oblik argumenta koji želimo da uhvatimo a zatim i vrednost funkcije za takav argument. Na primer, funkciju tipa dupliraj :: Int -> Int koja duplira argument možemo definisati sa:

dupliraj :: Int -> Int
dupliraj x = 2 * x

Ovo je primer trivijalnog podudaranja oblika. Ovde x predstavlja oblik proizvoljnog broja i ne vrši se nikakvo grananje.

Kao što vidimo, navedenom sintaksom oslobodili smo se definicije funkcija preko lambda izraza. I zaista, gotovo uvek ćemo umesto sintakse za lambda apstrakciju koristiti podudaranje oblika, pa čak i kada u funkciji nema grananja.

Ipak, sintaksa podudaranja oblika je veoma zgodna za grananje. U najjednostavnijem slučaju, to grananje se sastoji u tome da se "uhvati" određena vrednost argumenta. Na primer funkcija f koja slika 0 u 1 a sve ostale brojeve u 0, može biti ovako definisana:

f :: Int -> Int
f 0 = 1
f x = 0

Naravno, funkciju f smo mogli definisati lako i uz pomoć guards ili if then else sintakse.

Dakle sa kodom f 0 "uhvaćena je" posebna vrednost argumenta. Kao i kod guards sintakse, pri podudaranju oblika slučajevi se proveravaju redom, odozdo ka dole. Zato je naredna funkcija konstantna:

f' :: Int -> Int
f' x = 0
f' 0 = 1

U ovom slučaju, prva linija "hvata" oblik svakog argumenta, i nikad neće doći do provere druge linije. Prema tome, f' 0 će se evaluirati u 0.

Naravno, moguće je navesti proizvoljno mnogo slučajeva:

daLiJeCifra :: Char -> Bool
daLiJeCifra '0' = True
daLiJeCifra '1' = True
daLiJeCifra '2' = True
daLiJeCifra '3' = True
daLiJeCifra '4' = True
daLiJeCifra '5' = True
daLiJeCifra '6' = True
daLiJeCifra '7' = True
daLiJeCifra '8' = True
daLiJeCifra '9' = True
daLiJeCifra x = False

Funkcija koja proverava da li dati karakter reprezentuje cifru.

U navedenom primeru, poslednja linija koda, odnosno daLiJeCifra x = False "hvata" svaki argument. Ali kao što vidimo, povratna vrednost funkcije, ne zavisi od vrednosti uhvaćenog argumenta. U ovakvim situacijama, može se koristiti znak _ koji predstavlja argument koji ne želimo da vezujemo za ime. U ovom kontekstu, znak _ nazivamo džoker⁸.

Koristeći džoker, poslednju liniju prethodnog primera možemo da zamenimo sa daLiJeCifra _ = False. Ako se vratimo na pretposlednji primer (funkcija f koja slika 0 u 1 a sve ostale brojeve u 0), ta funkcija može biti definisana i sa

f :: Int -> Int
f 0 = 1
f _ = 0

Sa podudaranjem oblika, možemo lako definisati i funkcije više argumenta. Tako na primer naredna dva koda definišu istu funkciju:

g :: Int -> Int -> Int
g = \x y -> x + 2*y

g :: Int -> Int -> Int
g x y = x + 2*y

Možemo i da "pomešamo" sintaksu lambda apstrakcije i sintaksu podudaranja oblika i da napišemo sledeći kod

g :: Int -> Int -> Int
g x = \y -> x + 2*y

Sintaksu podudaranja oblika možemo da shvatimo na sledeći način: kada g primenimo na neku vrednost x, tada dobijamo funkciju \y -> x + 2*y.

Uređene \(n\)-torke se takođe mogu dekonstruisati podudaranjem oblika.

Primer 6.

Funkciju saberi :: (Double, Double) -> Double koja sabira koordinate uređenog para možemo definisati sa narednim kodom

saberi :: (Double, Double) -> Double
saberi (x, y) = x + y

Primer 7.

Funkicju saberi3 koja sabira koordinate uređene trojke možemo definisati na sledeći način

saberi3 :: (Double, Double, Double) -> Double
saberi3 (x, y, z) = x + y + z

Iz dva navedena primera, vidimo da nam funkcije poput fst ili snd nisu neophodne.

Zadatak 4. Implementirati funkciju fst3 :: (a, b, c) -> a koja vraća prvu koordinatu uređene trojke.

fst3 :: (a, b, c) -> a
fst3 (x, _, _) = x

Pošto ne koristimo vrednosti druge i treće kordinate, te vrednosti ne moramo da vezujemo novim imenom, već možemo iskoristi džoker.

Zadaci

Zadatak 5. Sa uređenom trojkom (Double, Double, Double) može se prezentovati vektor trodimenzionalne ravni. Napisati funkcije za zbir, skalarni i vektorski proizvod dva vektora, kao i funkciju koja skalira vektor za dati koeficijent i funkciju koja računa dužinu vektora.

Zadatak 6. Reimplementirati funkciju daLiJeCifra bez korišćenja bilo koje sintakse za grananje.

Možemo iskoristiti funkciju elem :: Eq a -> a -> [a] -> Bool koja proverava da li se element nalazi u listi:

daLiJeCifra = \x -> elem x "0123456789"