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:

  1. 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.
  2. 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.
  3. 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.
  4. Apstrakcija je desnoasocijativna. Npr. umesto \x -> (\y -> x + y) pišemo \x -> \y -> x + y.
  5. 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 funkcije, 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.

Primer 3.

U prethodnoj 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 koristeć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 Haskelu2. 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:

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:

  1. Uslov (izraz između if i then klauze) mora biti tipa Bool.
  2. Moraju se navesti povratne vrednosti za oba slučaja (u suprotnom izraz bi mogao biti nedefinisan u zavisnosti od vrednosti uslova).
  3. 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 

Ograđene definicije

Ograđena definicija3 je poseban oblik definicije funkcije koja omogućava pregledno testiranje više uslova. Svaki od uslova je logički izraz koji se navodi nakon vertikalne crte |, a nakon uslova postavlja se povratna vrednost funkcije.

Ograđena definicija ne predstavlja izraz4. Opšti oblik ograđenih definicija bi bio5:

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 ograđenih definicija 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 ograđenim definicijama 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 intenziteta6. 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. Dodat 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 nisu7. 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 ograđene definicije postavi konstanta otherwise koja je ime za vrednost True8:

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 ograđenom definicijom, 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 oblika9 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žoker10.

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.

Podudaranje oblika liste

Tehnika podudaranja oblika je veoma korisna pri radu sa listama. Tada lako možemo da uhvatimo praznu, jednočlanu, dvočlanu listu, itd... ili da rastavimo listu na glavu i rep.

Primer 6.

Funkciju koja proverava da li je lista celih brojeva prazna11, možemo definisati na sledeći način:

prazan :: [Int] -> Bool
prazan [] = True
prazan x = False
Slučaj prazne liste je uhvaćen sa oblikom [], dok su svi ostali slučajevi obuhvaćeni generičkim promenljivom x.

Neophodno je obuhvatiti sve moguće oblike promenljive. Ako se neki od oblika izostavi, definisana funkcija neće biti totalna, i za neke od argumenata će doći do izuzetka:

prazan' :: [Int] -> Bool
prazan' [] = True
ghci> prazan' [1, 2, 3]
*** Exception: main.hs:3:1-15: Non-exhaustive patterns in function prazan'

Na primer, ako želimo da napišemo funkciju s :: [Int] -> Int koja praznoj listi dodeljuje \(0\), jednočlanoj listi dodeljuje element te liste, dvočlanoj listi dodeljuje zbir dva elementa, a svim ostalim listama dodeljuje \(1\), korišćenjem guards sintakse dobijamo naredni kod:

s :: [Int] -> Int
s xs 
  | xs == [] = 0
  | len xs == 1 = xs !! 0
  | len xs == 2 = xs !! 0 + xs !! 1
  | otherwise = 1

Korišćenjem podudaranja oblika dobijamo elegantniji kod:

s :: [Int] -> Int
s [] = 0
s [x] = x
s [x, y] = x + y
s _ = 1

Kao što vidimo, podudaranjem oblika liste dekonstruisali smo neke moguće oblike argumenta funkcije. U trećoj liniji definisali smo funkciju u slučaju kada je njen argument jednočlana lista [x]. Imenom x ovde smo "vezali" član te jednočlane liste. Slično, u narednoj liniji koda, dekonstruisali smo dvočlane liste. U ovom slučaju, prvi element je predstavljen imenom x a drugi element imenom y.

Moguće je takođe koristi činjenicu da se lista poput [x, y, z] može predstaviti kao x:[y,z] ili x:y:[z] ili x:y:z:[]. Tako je prethodni primer moguće napisati i kao

s :: [Int] -> Int
s [] = 0
s (x:[]) = x
s (x:y:[]) = x + y
s _ = 1
Primer 7.

Funkcija koja vraća rep liste (sve element osim prvog), može se definisati na sledeći način:

rep :: [a] -> a
rep (x:xs) = xs
Operator : nadovezuje element na početak liste. Prema tome x je prvi element, a xs predstavlja ostatak liste. Primetimo da ova funkcija nije totalna jer nije definisana za slučaj prazne liste.

Zapravo, pošto nas u navedenom kodu vrednost x ne interesuje, funkciju možemo definisati i sa džokerom:

rep :: [a] -> a
rep (_:xs) = xs
Džokere bi trebalo koristiti kad god je to moguće, jer poboljšavaju čitljivost koda tako što umanjuju broj vezanih imena.

Dobro je naglasiti da pri podudaranju oblika nije moguće navesti oblik koji sadrži operator ++ (na primer ne možemo uhvatiti dvočlanu listu sa [x] ++ [y]). Razlog zašto je operator : moguće koristiti, a ++ ne, postaće jasan u jednoj od narednih lekcija.

Podudaranje oblika \(n\)-torke

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

Primer 8.

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

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

Podudaranje oblika unutar lambda izraza

U lambda izrazima moguće je upotrebiti podudaranje oblika za dekonstrukciju argumenta Zbog same forme lambda izraza, moguće je navesti samo jedan oblik po kom se vrši podudaranje. Taj oblik postavljamo između "lambde" i strelice.

Primer 10.

Funkciju head možemo elegantno da definišemo kao \(x:xs) -> x. Naravno, ova funkcija neće biti totalna, jer slučaj prazne liste nije obrađen (niti može biti obrađen ako je funkcija definisana sa lambda izrazom).

Podudaranje oblika u lambda izrazima retko se koristi sa listama, baš iz razloga zato što možemo proveriti samo jedan oblik argumenta (što je retko kad dovoljno u slučaju lista). Ali, kako je oblik uređenih \(n\)-torki u potpunosti određen tipom, sa takvim tipovima se često koristi podudaranje oblika u lambda izrazima.

Primer 11.

Umesto funkcija fst i snd možemo koristiti lambda funkcije \(x, y) -> x i \(x, y) -> y.

Zadaci

Zadatak 4. 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 5. Reimplementirati funkciju daLiJeCifra :: Char -> Bool 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 :: Char -> Bool
daLiJeCifra x = elem x "0123456789"