Funktori

Koncept funktora je važan za Haskel. Iako isprva deluje kao nepotrebno apstraktan pojam, funktori zapravo opisuju veoma prirodnu transformaciju.

Pojam funktora je preuzet iz apstraktnih oblasti matematike, ali se u Haskelu taj pojam svodi na klasu tipova. Pre nego što tačno definišemo nove pojmove, pokušaćemo da damo motivaciju.

Funktori

Motivacija

U jednoj od prethodnih lekcija, upoznali smo se sa apstraktnim tipom Maybe :: * -> *. Kao što smo tada videli, Maybe A je tip koji osim vrednosti tipa A sadrži i vrednost Nothing koja predstavlja odsustvo vrednosti tipa A.

Zamislimo sada da od neke funkcije dobijamo vrednost tipa Maybe Float¹. Ako želimo dalje da obrađujemo vrednost, moramo se osloboditi Maybe omotača:

dupliraj :: Maybe Float -> Float
dupliraj (Just a) = 2 * a

Nažalost funkcija dupliraj nije totalna. Ako joj prosledimo vrednost Nothing doći će izuzetka i program će biti prekinut. Dakle, moramo vratiti vrednost tipa Float i u slučaju kada je prosleđena vrednost Nothing. Stoga funkcija sada izgleda ovako:

dupliraj :: Maybe Float -> Float
dupliraj (Just a) = 2 * a
dupliraj Nothing = 0

Funkcija dupliraj je sada totalna, ali uočavamo drugi problem: izgubili smo informaciju koju Maybe tip nosi u sebi. Sada više ne možemo razlikovati vrednost 0 koja je "došla" iz Just 0 od one koja je "došla" od Nothing. Ponekad je dozvoljeno napraviti takav gubitak informacije, ali često postoje i situacije kada nije. Zbog toga, definisaćemo funkciju dupliraj':

dupliraj' :: Maybe Float -> Maybe Float
dupliraj' (Just a) = 2 * a
dupliraj' Nothing = Nothing

Primetimo da je kodomen funkcije dupliraj' ponovo možda-tip. Dakle, ako smo mislili da vrednost dobijenu primenom funkcije dupliraj prosledimo nekoj narednoj funkciji f :: Float -> A, tada moramo na sličan način definisati i funkciju f' :: Maybe Float -> Maybe A. Zaista, već smo ustanovili da verovatno ne želimo funkciju tipa Maybe Float -> A jer se takvom funkcijom gubimo informaciju koju možda-tip pruža. Stoga je potrebno svaku funkciju definisati u "možda-obliku", baš kao dupliraj i dupliraj'.

Na prvi pogled sve je u redu, jer je takve funkcije neznatno teže definisati. Ali kako budemo razvijali sve veći program, primetićemo da pišemo mnogo koda na potpuno isti način. Od funkcije f :: A -> B kreiraćemo funkciju f' :: Maybe A -> Maybe B, kodom poput sledećeg:

f' :: Maybe A -> Maybe B
f' (Just a) = Just (f a)
f' Nothing = Nothing

Navedeni postupak je jednostavan, ali neprijatan za ponavljanje. Zbog toga želimo da konstruišemo jednu polimorfnu funkciju višeg reda koja će nas osloboditi zamornog kopiranja koda. Ta funkcija će kao parametar imati funkciju f :: a -> b a vratiće funkciju tipa Maybe a -> Maybe b. Na osnovu opisa nije teško napisati definiciju:

maybeMap :: (a -> b) -> Maybe a -> Maybe b 
maybeMap f (Just a) = Just (f a)
maybeMap _ Nothing = Nothing

Sada se dupliraj'' može² elegantnije definisati:

dupliraj'' :: Maybe Float -> Maybe Float
dupliraj'' = maybeMap (2*)

Rečeno žargonom Haskel programera, funkcija maybeMap podiže funkciju tipa a -> b u funkciju tipa Maybe a -> Maybe b. Više nije neophodno svaku funkciju redefinisati tako da radi sa možda-tipovima, maybeMap na jedan uniforman način to radi za nas.

Kada radimo sa više funkcija, tada maybeMap možemo da iskoristimo sa operatorom kompozicije. Umesto da posebno od f :: A -> B i g :: B -> C definišemo odgovarajuće funkcije f' :: Maybe A -> Maybe B i g' :: Maybe B -> Maybe C, možemo jednostavno da maybeMap primenimo na g . f: maybeMap (g . f) :: Maybe A -> Maybe C. Ova kompozicija se mogla zapisati i kao maybeMap g . maybeMap f. Zaista maybeMap (g . f) primenjena na vrednost Just x je po definiciji Just (g (f x)), a maybeMap g . maybeMap f primenjena na vrednost Just x je maybeMap g (maybeMap f (Just x)) odnosno maybeMap g (Just (f x)), odnosno Just (g (f x)). I analogno se dokazuje jednakost i za Nothing vrednost³.

Funkcija maybeMap ima još jednu zanimljivu osobinu: naime, važi jednakost (maybeMap id) v = v za svaku vrednost v :: Maybe A⁴. Odavde sledi da je maybeMap id upravo identička funkcija na Maybe A!

Opisane osobine funkcije maybeMap već smo videli ranije u drugom kontekstu: funkcija map :: (a -> b) -> [a] -> [b] primenjuje datu funkciju na svaki element date liste i vraća dobijeno listu. Ali map možemo takođe da shvatimo kao podizanje funkcije tipa a -> b u funkciju tipa [a] -> [b], jer kada map primenimo na neku funkciju f :: A -> B, dobijamo funkciju tipa [A] -> [B]. Takođe, za funkciju map važe iste osobine: kompozicija map g . map f je ista kao kompozicija map (g . f)⁵, i map id je identička funkcija.

Vidimo da je funkcija map analogna funkciji maybeMap, s tim što se maybeMap odnosi na apstraktni tip Maybe :: * -> * dok se map odnosi na apstraktni tip [] :: * -> *. Oba navedena tipska konstruktora možemo da shvatimo kao funkcije koje od nekog tipa A prave tip strukture koje sadrže vrednosti (ili vrednost) tipa A⁶. Odgovarajuće funkcije map i maybeMap omogućuju primenu neke funkcije na vrednosti koje su "upakovane" u ovim strukturama, pri čemu same strukture ostaju nepromenjene.

Kad god imamo kolekciju tipova (u ovom slučaju apstraktnih) i odgovarajućih funkcija koji imaju iste osobine, zgodno je da te tipove okupimo u jedinstvenu klasu, a odgovarajuće funkcije predstavimo zajedničkim imenom. Upravo zato uvodimo Functor klasu.

Definicija Functor klase

U Haskel jeziku, Functor je klasa tipova koja propisuje jednu funkciju i jedan operator:

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    (<$) :: a -> f b -> f a
    (<$) = fmap . const
    {-# MINIMAL fmap #-}

Prvo što bi trebalo da uočimo jeste da konkretni tipovi (tipovi vrste *) ne mogu pripadati ovoj klasi, jer je fmap tipa (a -> b) -> f a -> f b iz čega sledi da f mora biti apstraktni tip vrste * -> *⁷.

Ono što nismo naveli u kodu su dva zakona koja fmap mora da zadovoljava:

1. Funktor mora da čuva identičku funkciju, tj. mora da važi fmap id = id.
2. Funktor mora da čuva kompoziciju funkcija, tj. mora da važi fmap g . fmap h = fmap (g . h).

Kompajler ne može proveriti da li su navedeni zakoni zadovoljeni. Na programeru je da osigura da implementacija fmap za određenu instancu zadovoljava zakone. Svaki apstraktni tip koji je instanca Functor klase nazivamo funktor.

Operator <$ koji je naveden u definiciji klase predstavlja podizanje const funkcije. Govoreći rečnikom struktura od malopre, sa operatorom <$ zamenjuju se sve vrednosti u strukturi sa istom vrednošću. Ovaj operator je definisan preko fmap funkcije, i nije ga potrebno implementirati.

instance Functor [] where
    fmap = map

ghci> True <$ [1,2,3,4,5]
[True,True,True,True,True]

instance Functor Maybe where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

ghci> 2 <$ Just 7
Maybe 2
ghci> 2 <$ Nothing
Nothing

instance Functor ((,) a) where
    fmap f (x,y) = (x, f y)

ghci> fmap (+10) (1, 2)
(1, 12)
ghci> "Haskel" <$ (True, 2)
(True, "Haskel")

U modulu Data.Functor definisane su mnoge instance poput navedenih. U ovom modulu je takođe definisan operator podizanja <$> :: Functor f => (a -> b) -> f a -> f b kao sinonim za funkciju fmap. Ovaj operator smo već predstavili u lekciji o operatorima ali samo u kontekstu lista. Za razliku od <$, operator podizanja se zaista često koristi.

Zadatak 1. Neka je definisan apstraktni tip trodimenzionalnog vektora data V3 a = V3 a a a. Definisati instancu Functor V3.

Aplikativni funktori

Problem sa Maybe funktorom

Koliko god da je pojam funktora koristan, ipak nije mnogo zgodan sa rad sa funkcijama više promenljiva. Na primer, ako želimo sabrati dve Maybe Int vrednosti, moramo implementirati funkciju poput maybeSum:⁸:

maybeSum :: Maybe Int -> Maybe Int -> Maybe Int
maybeSum (Just a) (Just b) = Just $ a + b
maybeSum  _        _       = Nothing

Lako je definisati funkciju poput maybeSum, ali kao i ranije, ne želimo da ponavljamo kod. Umesto toga, želimo da već postojeće funkcije od dva (ili više) argumenta podignemo na uniforman način do funkcija koja "rade" sa možda-tipovima. Kao što funkcija fmap omogućava da funkciju tipa a -> b primenimo na (vrednost tipa) Maybe a i dobijemo Maybe b, tako sad želimo način da funkciju tipa a -> b -> c primenimo na Maybe a i Maybe b i dobijemo Maybe c. Imitirajući implementaciju maybeSum stižemo do funkcije maybeMap2:

maybeMap2 :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
maybeMap2 f (Just a) (Just b) = Just $ f a b
maybeMap2 _  _        _       = Nothing

Funkcija maybeMap2 značajno olakšava rad sa funkcijama dva argumenta, ali ne rešava problem sa funkcijama tri i više argumenata. Naravno, lako možemo implementirati odgovarajuće funkcije maybeMap3, maybeMap4, maybeMap5, ... ali nas to ponovo vodi ka ružnom kodu⁹. I dalje nećemo imati uniforman način podizanja funkcija više argumenata na nivo možda-tipova.

Vratimo se korak u nazad, i pogledajmo zašto dobro poznata funkcija fmap nije zgodna za rad sa funkcijama dve promenljive. Neka je sum' = (+) :: Int -> Int -> Int. Primenom fmap na sum' i jednu Maybe vrednost dobijamo funkciju "upakovanu" u Maybe strukturu:

ghci> sum' = (+) :: Int -> Int -> Int
ghci> s = fmap sum' (Just 2)
ghci> :t s
s :: Maybe (Int -> Int)

Zašto ovo ima smisla? Tip funkcije sum' je Int -> Int -> Int, odnosno eksplicitnije napisano Int -> (Int -> Int). Ako funkcija fmap :: Functor f => (a -> b) -> f a -> f b uzima za prvi argument funkciju tipa a -> b, tada će u slučaju funkcije sum', tipska promenljiva a biti Int a promenljiva b biti Int -> Int. Stoga je i fmap sum' :: Functor f => f Int -> f (Int -> Int) odnosno fmap sum' (Just 2) :: Maybe (Int -> Int). Vrednost tipa Maybe (Int -> Int) predstavlja unarnu funkciju u Maybe strukturi. Setimo se da mi želimo da f primenimo na dve Maybe Int vrednosti, a vrednost s je nastala primenom na jednu vrednost. Stoga je potrebno funkciju u vrednosti s primeniti na još jednu Mayb Int vrednost. Zato ćemo definisati maybeApply funkciju¹⁰:

maybeApply :: Maybe (a -> b) -> Maybe a -> Maybe b
maybeApply (Just f) (Just x) = Just $ f x
maybeApply  _        _       = Nothing

Sa funkcijom maybeApply možemo završiti prethodni primer iz terminala:

ghci> sum' = (+) :: Int -> Int -> Int
ghci> s = fmap sum' (Just 2)
ghci> maybeApply s (Just 3)
Just 5

Ako koristimo operator podizanja <$> (koji je sinonim za fmap) a maybeApply postavimo u infiksni oblik, kôd možemo elegantnije zapisati:

ghci> (sum' <$> Just 2) `maybeApply` (Just 3)
Just 5
ghci> (sum' <$> Nothing) `maybeApply` (Just 3)
Nothing
ghci> (sum' <$> Just 2) `maybeApply` Nothing
Nothing

Lepota ovog pristupa je što na sličan način možemo postupiti sa funkcijama više promenljiva. Na primer, neka je data neka funkcija g :: A1 -> A2 -> A3 -> B. Ako je m1 neka vrednost tipa Maybe A1, tada je g <$> m1 :: Maybe (A2 -> A3 -> B). Na ovu vrednost možemo da delujemo sa maybeApply funkcijom. Ako je m2 neka vrednost Maybe A2 tipa, tada je (g <$> m1) `maybeApply` m2 :: Maybe (A3 -> B). Naravno, maybeApply nam opet omogućava da možda-funkciju primenimo na možda-vrednost. Tačnije ((g <$> m1) `maybeApply` m2) `maybeApply` m3 je vrednost tipa Maybe B. Funkciju maybeMap2 od ranije možemo sada definisati i ovako:

maybeMap2 :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
maybeMap2 f a b = (f <$> a) `maybeApply` b 

Aplikativni funktori

Vratimo se na opšti primer funktora f :: * -> *. Ako želimo da funkciju proizvoljne arnosti podignemo na nivo funktora f neophodno je da posedujemo funkciju koja će vrednost tipa f (A -> B) transformisati u vrednost tipa f A -> f B, baš kao što maybeApply transformiše Maybe (A -> B) u Maybe A -> Maybe B. Videli smo da je takvu funkciju zgodno koristiti u infiksnom obliku, te ćemo je stoga definisati kao operator <*> kog nazivamo operator aplikacije funktora. Dakle, za neke funktore f možemo zahtevati postojanje operatora (<*>) :: f (a -> b) -> f a -> f b. Takve funktore nazivamo applikativni funktori, jer dozvoljavaju neku vrstu aplikacije funkcije na vrednost.

Mi smo se već do sada upoznali sa "klasičnim" operatorom aplikacije ($) :: (a -> b) -> a -> b. Operator podizanja (<$>) :: (a -> b) -> f a -> f b može se takođe¹¹ shvatiti kao neka vrsta operatora aplikacije. Operator <$> aplicira funkciju tipa a -> b na vrednost tipa f a. Operator (<*>) :: f (a -> b) -> f a -> f b takođe u nekom smislu vrši apliciranje funkcije na vrednost. Primetimo koliko su tipovi ova tri operatora međusobno slična.

Naravno, ne možemo očekivati da će svaka implementacija funkcije <$> biti dobra. Na primer, da smo maybeApply funkciju, koja jeste operator aplikacije funktora za Maybe, definisali kao konstantnu funkciju, tada ne bismo mogli smisleno da podižemo ostale funkcije:

maybeApply :: Maybe (a -> b) -> Maybe a -> Maybe b
maybeApply  _        _       = Nothing

ghci> (sum' <$> Just 2) `maybeApply` (Just 3)
Nothing

Zbog toga, za operator <*> zahtevaćemo neke osobine (zakone), baš kao što smo zahtevali zakone za fmap.

Definicija Applicative klase

Kao i u slučaju funktora, pojam aplikativnog funktora formalizovaćemo kroz klasu. Klasa Applicative je definisana na sledeći način.

class Functor f => Applicative f where
    pure :: a -> f a

    (<*>) :: f (a -> b) -> f a -> f b
    (<*>) = liftA2 id

    liftA2 :: (a -> b -> c) -> f a -> f b -> f c
    liftA2 f x = (<*>) (fmap f x)

    (*>) :: f a -> f b -> f b
    a1 *> a2 = (id <$ a1) <*> a2

    (<*) :: f a -> f b -> f a
    (<*) = liftA2 const

    {-# MINIMAL pure, ((<*>) | liftA2) #-}

Prvo što uočavamo u dekleraciji klase, je klasno ograničenje Functor f => Applicative f kojim se zahteva da sve instance klase Applicative budu instance i klase Functor. Nakon dekleracija funkcija, navedena je i pragma koja označava da svaka Applicative instanca sadrži implementaciju pure funkcije, kao i barem jednu od implementacija <*> i liftA2 funkcija (otuda njihovo navođenje unutar ( | ), nalik na algebarsku sumu).

Sa operatorom <*> :: f (a -> b) -> f a -> f b smo se već upoznali u prethodnim redovima: ovaj operator primenjuje funkciju "upakovanu" u f funktor na vrednost koja je takođe "upakovana" u f. Videli smo da operator <*> dozvoljava podizanje funkcija više promenljiva na nivo funktora. Funkcija liftA2 je specijalan slučaj ovakvog podizanja: to je funkcija koja podiže funkciju dva argumenta. Naravno, liftA2 je moguće definisati preko fmap i <*> što smo i prikazali gore¹². Zanimljivo je da je moguće uraditi i suprotno: definisati funkciju <*> preko funkcije liftA2. Ta definicija¹³ je i data u definiciji klase: (<*>) = liftA2 id. Prema tome, <$> i liftA2 definišu jedna drugu, i dovoljno je implementirati jednu od ovih funkcija.

Funkcija pure :: a -> [a] predstavlja funkciju koja proizvoljnu vrednost "obmotava" u funktor, odnosno proizvoljnu vrednost podiže. Do sada smo se susretali sa pojmom podizanja, ali nismo zahtevali od funktora da podiže bilo koju vrednost, već samo funkcije. Na primer, u slučaju funktora Maybe, pure je baš konstruktor Just, dok je u slučaju funktora [] funkcija pure definisana kao \x -> [x]. U produžetku ćemo videti zašto je u ovim primerima funktora neophodno definisati pure baš ovako.

Funkcije *> i <* su definisane preko ostalih, i njih ćemo pojasniti kasnije.

Kao smo nagovestili, kao i u slučaju fmap funkcije, funkcije Applicative klase moraju zadovoljavati neke zakonitosti. Ove zakonitosti se odnose na <*> i pure, ali se mogu formulisati i za liftA2 i pure. Zakoni su sledeći:

1. fmap f x = pure f <*> x.
2. pure id <*> v = v.
3. u <*> pure y = pure ($ y) <*> u.
4. pure (.) <*> u <*> v <*> w = u <*> (v <*> w).
5. pure f <*> pure x = pure (f x).

Iako zakoni deluju komplikovano, zapravo su veoma prirodni. Kroz naredne primere videćemo konkretna značenja zakona.

Možda-tipovi kao aplikativni funktori

Kako smo same aplikativne funktore motivisali sa možda tipovima, nije iznenađujuće da je Maybe aplikativni funktor. Instanca Applicative Maybe je definisana na sledeći način

instance Applicative Maybe where
    pure = Just

    Just f  <*> m = fmap f m
    Nothing <*> _ = Nothing

Sa definicijom <*> u kontekstu možda-tipova smo se upoznali gore. Primenom Just f na Just v, želimo Just (f v), dok primenom Just f na Nothing želimo Nothing. Međutim, to je upravo definicija za fmap f m. Sa druge strane, ako nam je umesto upakovane funkcije data Nothing vrednost, tada svakako želimo da vratimo Nothing.

Funkcija pure je implementirana tako da vrednost pakuje u Just funktor (tj. pure x = Just x). Možemo se zapitati zašto smo odabrali ovakvu definiciju, a ne pure x = Nothing. Razlog je sasvim jednostavan, ako bi bilo pure x = Nothing, tada bi pure f <*> x bilo Nothing <*> x odnosno Nothing, a to se razlikuje od fmap f x koje se svodi naravno na Just (f x). Dakle, prvi zakon aplikativnih funktora bi bio prekršen. Sa druge strane, definicija pure x = Just x je saglasna sa prvim zakonom jer je tada pure f <*> x baš Just f <*> x odnosno Just (f x).

Što se tiče ostalih zakona, oni se lako mogu proveriti. Drugi zakon je jednostavan i on nam govori da podizanje identičke funkcije mora biti identička funkcija u smislu aplikacije <*>. Konkretno pure id je po definiciji Just id, pa je pure id <*> v = v bez obzira da li je v oblika Nothing ili Just x.

Treći zakon je sličan drugom, i on se odnosi na podizanje sekcije $ y. Važi da je Nothing <*> pure y = Nothing = (Just ($ y)) <*> Nothing = pure ($ y) <*> Nothing kao i (Just f) <*> pure y = Just (f y) = (Just ($ y)) <*> (Just f) = pure ($ y) <*> (Just f), te je i treći zakon zadovoljen.

Četvrti zakon se odnosi na podizanje operatora kompozicije. Kratko rečeno, želimo da podizanje operatora kompozicije bude funkcija koja će vršiti kompoziciju. Napomenimo, da je <*> definisan kao levoasocijativan operator (kod definicije same klase Applicative). Za Maybe funktor možemo lako proveriti da zakon važi. Pretpostavimo da je u = Just _u, v = Just _v i w = Just _w., tada je pure (.) <*> u <*> v <*> w = ((Just (.) <*> Just _u) <*> Just _v) <*> Just _w = (Just (_u .) <*> Just _v) <*> Just _w = Just (_u . _v) <*> Just _w = Just ((_u . _v) _w) = Just (_u (_v _w)) = Just _u <*> Just (_v _w) = Just _u <*> (Just _v <*> Just _w) = u <*> (v <*> w) Na sličan način se mogu dokazati i jednakosti kada je jedna od vrednosti u, v ili w jednaka Nothing.

Peti zakon se značajno jednostavnije proverava: pure f <*> pure x = (Just f) <*> (Just x) = Just (f x) = pure (f x).

Zadatak 2. Neka je funkcija inverz :: Float -> Maybe Float definisana sa inverz x = if x == 0 then Nothing else Just x. Definisati funkciju harm :: Float -> Float -> Maybe Float koja vraća harmonijsku sredinu \[\frac{2}{\frac 1 x + \frac 1 y}\] dva broja \(x\) i \(y\). Ako je jedan od brojeva nula, tada vratiti Nothing. Definisati funkciju korišćenjem metoda Applicative klase i funkcije inverz.

Strelice kao funktori

Još od prvih lekcija, koristili smo konstruktor ->, takozvanu strelicu, za konstrukciju tipa funkcija. Tokom prvih lekcija to nismo znali, ali strelica je binarni tipski konstruktor, u šta se smo se uverili u glavi o vrstama.

Kako je strelica vrste * -> * -> *, strelica ne može biti funktor¹⁴, ali ako fiksiramo jedan od argumenata, dobićemo tip odgovarajuće vrste. Za konkretan primer tokom narednog izlaganja odabraćemo Int kao tip koji ćemo fiksirati za domen ili kodomen. Da bi olakšali zapis, kreirajmo dva nova tipa:

type FromInt a = Int -> a

type ToInt a = a -> Int

Tipovi FromInt i ToInt su tipovi koji potencijalno mogu biti funktori jer poseduju odgovarajuću vrstu:

ghci> :kind FromInt
FromInt :: * -> *
ghci> :kind ToInt
ToInt :: * -> *

Tip FromInt T predstavlja tip svih funkcija iz celih brojeva u T, dok ToInt T predstavlja tip svih funkcija iz T u tip celih brojeva. Za početak, posvetimo se tipu FromInt.

Za definiciju instancu Functor FromInt, neophodno i dovoljno je definisati metodu fmap :: (a -> b) -> FromInt a -> FromInt b, tj, raspisujuci definiciju sinonima, fmap :: (a -> b) -> (Int -> a) -> (Int -> b). Definisanje metode fmap se svodi na definisanje funkcije tipa Int -> B ako su nam date funkcije f :: A -> B i g :: Int -> A. Kao što i naredna ilustracija pokazuje, nemamo mnogo izbora za definiciju: jedino sto možemo da uradimo je da napravimo kompoziciju f . g :: Int -> B:

Definicija instance je zapravo najkraća do sada:

instance Functor FromInt where
    fmap f g = f . g

Naravno, neophodno je i da proverimo dva zakona funktora.

Prvo, da li je fmap id identička funkcija. Naravno da jeste, jer je id neutralni element za kompoziciju tj. fmap id g = id . g = g.

Drugo, da li je fmap distributivno u odnosu na kompoziciju? Kako je fmap (f2 . f1) g = (f2 . f1) . g = f2 . (f1 . g) = f2 . (fmap f1 g) = fmap f2 (fmap f1 g) = (fmap f2 . fmap f1) g za svako g, sledi da je fmap (f2 . f1) = fmap f2 . fmap f1, pa je zadovoljen i drugi zakon funktora.

f :: Bool -> String
f b = show b

g :: FromInt Bool
g n = even n

ghci> m = fmap f g
ghci> :type m
FromInt String
ghci> m 2
"True"
ghci> m 3
"False"

Zadatak 3. Opisati operator <$ u kontekstu funktora FromInt.

Naravno, sledeći korak je da ucinimo FromInt aplikativnim funktorom. Za definisanje metode pure :: a -> (Int -> a) ponovo nemamo mnogo izbora. Ako nam je data jedna vrednost x :: A, možemo samo na jedan način konstruisati funkciju tipa A -> Int, a ta jedinstvena funkcija je konstantna funkcija: \_ -> x. Definicija <*> je nešto komplikovanija, ali nas ponovo tipovi vode ka rešenju. U kontekstu tipa FromInt, operator <$> poseduje tip (Int -> (a -> b)) -> (Int -> a) -> (Int -> b). Ako nam je data funkcija f :: Int -> (A -> B) i funkcija g :: Int -> A, tada možemo konstruisati funkciju tipa Int -> B tako što ćemo za svaku celobrojnu vrednost Int, aplicirati f i g na n, time dobiti vrednosti tipa A -> B i B, od kojih na očigledan način možemo dobiti vrednost tipa B. Kôd je ponovo sasvim jednostavan:

instance Applicative FromInt where
    pure x  = \_ -> x
    f <$> g = \n -> (f n) (g n)

Naravno, neophodno je dokazati da navedene definicije zadovoljavaju zakone aplikativnih funktora. Ovo ćemo prepustiti čitaocu, jer se ne razlikuje od provera koje smo do sada vršili.

Zadatak 4. Dokazati da gorenavedena instanca Applicative FromInt zadovoljava pet zakona aplikativnih funktora.

Kao i do sada, uvek želimo da uopštimo kôd, tako da se odnosi na što više tipova. Prethodni argumenti za tip FromInt mogu se od reči do reči ponoviti za bilo koji drugi tip. Stoga, za svaki tip T, učinićemo tip (->) T instancom klasa Functor i Applicative. Srećem, Haskel dozvoljava da ovakva opšta definicija izrazi kroz dekleraciju klase korišćenjem polimorfnog tipa (->) t. Upravo tako su i definisane instance strelice u prelidu:

instance Functor ((->) t) where
    fmap f g = f . g

instance Applicative ((->) t) where
    pure x  = \_ -> x
    f <$> g = \n -> (f n) (g n)

Vratimo se na tipski sinonim ToInt, koji konstruiše tip funkcija sa kodomenom Int. Da li je ovaj apstraktni tip funktor? Ako bi ToInt bio funktor, tada bismo od funkcija tipa g :: A -> B i f :: A -> Int mogli da konstruišemo funkciju tipa B -> Int. Međutim to je definitivno nemoguće, jer ako nam je data vrednost B, na tu vrednost ne možemo primeniti ni f ni g. Prema tome, ToInt ne može biti funktor, a samim tim ni aplikativni funktor. Isto važi i za svaki drugi apstraktni tip FuncToT a = a -> T.

Aplikativni parseri

Parser je program (ili funkcija) koji od niza nekih simbola generiše vrednosti. Najčešće parseri služe da se niske (liste karaktera) transformišu u neke vrednosti poput brojeva ili struktura podataka.

ghci> read "39.5" :: Float
39.5
ghci> read "[True, False]" :: [Bool]
[True, False]

Parsiranje je generalno težak problem. Stoga ne čudi što je tokom istorije računarstva razvijeno mnogo teorije o parserima i konkretnim tehnikama za njihovo konstruisanje. Svakako, teorija o parserima prevazilazi obime ove knjige, ali možemo ovde prikazati jednu tehniku za konstrukciju parsera. U pitanju su takozvani aplikativni parseri koji su realizovani uz pomoć aplikativnih funktora¹⁵.

Parsiranjem bi trebalo nisku (koja je lista karaktera) pretvoriti u neku vrednost tipa A. Na primer, parser celobrojnih brojeva bi trebalo da da nisku transformiše u vrednost tipa Float, a parser logičkih lista bi trebalo da nisku pretvori u vrednost tipa [Bool]. Stoga ćemo definisati novi (apstraktni) tip, koji može predstaviti parsere za vrednosti bilo kog tipa. Međutim, kroz ovaj novi tip je neophodno obezbediti par stvari.

1. Prvo, ne možemo očekivati da ćemo svaki parser konstruisati kao jedinstvenu funkciju, već kao kombinaciju manjih funkcija. Svaka od tih funkcija parsiraće jedan karakterističan deo niske (Na primer, parser Float vrednosti može biti sačinjen od tri parsera: prvog koji parsira ceo deo, drugog koji parsira tačku, i trećeg koji parsira razlomljeni deo. Slično, parser logičkih nizova može biti sačinjen od parsera koji parsira zagrade, parsera za literale logičke vrednosti, parsera za zarez, parsera za beline, itd...). Parsere ćemo kombinovati tako što će svaki naredni parser, parsirati ono "što ostane" nakon pokretanja prethodnih parsera. Stoga jedan parser vrednosti T neće vraćati samo vrednost tipa T, već uređen par tipa (String, T), gde prva koordinata označava ostatak niske koja se parsira.
2. Drugo, ne možemo očekivati da će svako parsiranje biti uspešno. Iz niske "Hi!" ne možemo parsirati broj niti logičku listu. Zbog toga, parser će zapravo vratiti možda-vrednost Maybe (String, T). Ako je parser uspeo, rezultat je oblika Just (s, x) za neku nisku s i vrednost x :: T. U suprotnom, parser vraća Nothing.

Uzimajući prethodno u obzir, stižemo do definicije tipa

newtype Parser a = P (String -> Maybe (String, a))

Sa navedenom definicijom tipa biće zgodna funkcija koja "pokreće" parser nad niskom:

parsiraj :: Parser a -> String -> Maybe (String, a)
parsiraj (P p) s = p s 

slovo :: Parser Char
slovo = P f
    where
        f [] = Nothing
        f (x:xs) = Just (xs, x)

ghci> parsiraj slovo "Hello world!"
Just ("ello world!", 'H')
ghci> parsiraj slovo ""
Nothing

cifra :: Parser Int
cifra = P f where
    f []     = Nothing
    f (x:xs) =
        if x `elem` ['1' .. '9']
        then Just (xs, fromEnum x - fromEnum '0')
        else Nothing

ghci> parsiraj cifra "9abc"
Just ("abc",9)
ghci> parsiraj cifra "1234"
Just ("234",1)
ghci> parsiraj cifra "Hello!"
Nothing

Zadatak 5. Kreirati funkciju maloSlovo :: Parser Char koja parsira samo mala latinična slova (tj. karakter iz raspona ['a' .. 'w']).

simbol :: Char -> Parser Char
simbol c = P $ \s -> case s of
    x:xs -> if x == c then Just (xs, c) else Nothing
    _   -> Nothing

ghci> parsiraj (simbol '.') ".Hello!"
Just ("Hello!",'.')
ghci> parsiraj (simbol '.') "Hello!"
Nothing

broj :: Int -> Parser Int
broj acc = P $ \s -> case parsiraj cifra s of
    Nothing -> Just (s, acc)
    Just (s', n) -> parsiraj (broj (acc*10 + n)) s'

ghci> parsiraj (broj 0) "123abc"
Just ("abc",123)

ghci> parsiraj (broj 987) "123ab"
Just ("aa",987123)
ghci> parsiraj (broj 56) "abc"
("abc", 56)

broj :: Parser Int
broj = P $ \s -> case parsiraj cifra s of
    Nothing -> Nothing
    Just (s', n) -> parsiraj (broj' n) s'
    where broj' acc = P $ \s -> case parsiraj cifra s of
            Nothing -> Just (s, acc)
            Just (s', n) -> parsiraj (broj' (acc*10 + n)) s'

*Main> parsiraj broj "123abc456"
Just ("abc456",123)
*Main> parsiraj broj "abc"
Nothing

Zadatak 6. Kreirati funkciju niska :: String -> Parser String koja na osnovu niske s kreira parser koji parsira isključivo s.

Sve što smo do sada videli o parserima, mogli smo da obradimo i u prethodnim lekcijama. Stoga je sada vreme da objasnimo zašto je tip Parser :: * -> * (aplikativni) funktor.

Metod fmap u kontekstu tipa Parse poseduje tip (a -> b) -> Parser a -> Parser b. To znači da ako su nam dati funkcija f :: A -> B i parser p :: Parser A, mi bi trebalo da konstruišemo parser tipa Parser B. Nemamo mnogo izbora nego da na rezultat parsiranja sa p primenimo funkciju f.

instance Functor Parser where
    fmap f p = P (\s -> fmap f' (parsiraj p s))
       where f' (x, y) = (x, f y)

Zadatak 7. Dokazati da navedena definicija poštuje dva zakona funktora.

instance Functor Parser where
    fmap f p = P (fmap (fmap f') (parsiraj p))
        where f' (x, y) = (x, f y)

instance Functor Parser where
    fmap f (P p) = P $ fmap (fmap (fmap f)) p

Nakon što smo ustanovili da je Parser funktor, možemo transformisati postojeće parsere.

ghci> parsiraj (fmap even cifra) "1234"
Just ("234",False)
ghci> parsiraj (fmap even cifra) "aaaa"
Nothing

Sledeći korak je implementirati instancu Applicative Parser. Za metodu pure :: a -> Parser a, nemamo mnogo izbora: to će biti "konstantan" parser koji ne parsira ništa. Za metodu <*> :: Parser (a -> b) -> Parser a -> Parser b takođe nemamo mnogo opcija. Ako nam je dat parser p1 :: Parser (A -> B) i parser p2 :: Parser A, sve što možemo da uradimo da bi dobili vrednost B je da "pokrenemo" parser p1 i onda sa dobijenim vrednostima "pokrenemo" parser p2. Naravno, ako neki od parsera ne uspe, tada ni "kombinacija" ovih parsera ne bi trebalo da uspe.

instance Applicative Parser where
    pure x = P $ \s -> Just (s, x)

    p1 <*> p2 = P $ \s -> primeni (parsiraj p1 s) p2
        where
            primeni Nothing       _ = Nothing
            primeni (Just (s',f)) p = parsiraj (fmap f p) s'

Zadatak 9. Dokazati da navedena definicija poštuje zakone aplikativnih funktora.

Parseri koji parsiraju funkciju (tj. vrednosti tipa oblika Parser (A -> B)) su na prvi pogled veoma čudan pojam. Šta uopšte znači parsirati funkciju iz niske karaktera? Ali, setimo se koja je bila motivacija za uvođenje aplikativnih funktora: aplikacija funkcija više promenljiva na vrednosti u funktorima. Od sada koristeći pure i <*> možemo kombinovati parsere koristeći proizvoljne funkcije.

ghci> f = \x y -> (x, y)
ghci> slovoCifra = f <$> slovo <*> cifra
ghci> parsiraj slovoCifra "D7"
Just ("",('D',7))

Kako operatori <* i *> funkcionišu u kontekstu parsera? Po definiciji, operator (<*) :: Parser a -> Parser b -> Parser a je definisan kao p1 <* p2 = liftA2 const p1 p2 što se svodi na p1 <* p2 = (fmap const p1) <*> p2. Ako je p1 :: Parser A, tada je fmap const p1 :: Parser (a -> Int) parser koji je moguće primeniti sa <*> na bilo koji drugi parser, ali će parsirana vrednost zavisiti samo od parsera p1, dok će parsirana vrednost parsera p2 biti ignorisana, pod uslovom da parser p2 uspe. Ako parser p2 nije uspešan, tada će i parser p1 <* p2 podbaciti. Slično je i sa operatorom (*>) :: f a -> f b -> f b koji ignoriše rezultat levog parsera (pod uslovom da je taj parser uspeo).

Navedeni operatori nam omogućavaju da konstruišemo parsere koji moraju parsirati neke delove niske, ali ti delovi ne utiču na parsiranu vrednost. Primer za ovu situaciju je parsiranje brojeva sa decimalnom tačkom: tačka se mora naći u zapisu decimalnog broja, ali ne utiče nikako na vrednost tog broja.

ghci> parsiraj (broj <* simbol '.') "123.456"
("456",123)

decimalanBrojSaTačkom :: Parser Double
decimalanBrojSaTačkom = f <$> (broj <* simbol '.') <*> broj
    where f x y = (fromIntegral x + (g $ fromIntegral y))
          g y = if y < 1 then y else g (y / 10)

ghci> parsiraj decimalanBrojSaTačkom "123.456"
Just ("",123.456)

niska :: String -> Parser String
niska ""     = P $ \s -> Just (s, "")
niska (x:xs) = P $ \s -> case parsiraj (simbol x) s of
    Just (s',_) -> parsiraj ((x:) <$> niska xs) s'
    Nothing     -> Nothing

ghci> parsiraj (niska "True") "Truehelloworld"
Just ("helloworld","True")
ghci> parsiraj (niska "False") "Falsebyeworld"
Just ("byeworld","False")
ghci> parsiraj (niska "hello") "bye"
Nothing

Parseri koje smo do sad konstruisali uglavnom su bili "atomični". Za kreiranje složenijih parsera, poput onih koji parsiraju čitav kôd nekog programskog jezika, potrebno je atomične parsere ukombinovati u složenije. Takvo ukombinovanje vršimo pomoću funkcija koje nazivamo parser kombinatori. Parser kombinatori uzimaju nekoliko parsera (najčešće istog tipa), i vraćaju parser.

Najjednostavniji primer parser kombinatora je funkcija koja uzima dva parsera i kreira novi parser koji pokušava da pokrene prvi ili drugi parser. Ovakav kombinator ima sasvim jednostavnu definiciju:

ili :: Parser a -> Parser a -> Parser a
ili p1 p2 = P $ \s -> case parsiraj p1 s of
    Just (s', v) -> Just (s', v)
    Nothing -> parsiraj p2 s

ghci> logičkaVrednost = niska "True" `ili` niska "False"
ghci> parsiraj logičkaVrednot "True"
Just ("","True")
ghci> parsiraj logičkaVrednot "False"
Just ("","False")

Zadatak 10. Definisati parser logičkeListe :: Parser [Bool] koji parsira liste logičkih vrednosti True i False. Na primer, parser bi trebalo da ispravno parsira nisku "[True,False]". Pretpostaviti da u nisci neće biti belina.

Zadatak 11. Definisati parser preskočiBeline :: Parser () koji samo preskače karaktere beline ' ', '\n' i '\t'.

Zadatak 12. Ponovo definisati parser logičkeListe :: Parser [Bool] ali tako da ispravno parsira niske u kojima se nalaze beline između logičkih vrednosti i zareza ili zagrada. Na primer, parser bi trebalo da ispravno parsira nisku poput "[ True, False ]".