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
1. 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
0
je proizvoljno odabrana, ilustracije radi.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
dupliraj'
je totalna i ispravno obrađuje vrednost 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
f :: A -> B
neka proizvoljna funkcijaNavedeni 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že2 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
vrednost3.
Funkcija maybeMap
ima još jednu zanimljivu osobinu: naime, važi jednakost (maybeMap id) v = v
za svaku vrednost v :: Maybe A
4. 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)
5, 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
6. 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 * -> *
7.
Ono što nismo naveli u kodu su dva zakona koja fmap
mora da zadovoljava:
- Funktor mora da čuva identičku funkciju, tj. mora da važi
fmap id = id
. - 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.
Kao što smo već nagovestili, apstraktni tip [] :: * -> *
je funktor. Instanca Functor []
je već definisana na sledeći način
instance Functor [] where fmap = map
Već smo videli da map
zadovoljava oba zakona, ali ponovimo to još jednom. Prvo,
fmap id [x₁, x₂, ... xₙ]
= [id x₁, id x₂, ... id xₙ]
= [x₁, x₂, ... xₙ]
što znači da je fmap id xs = xs
za svaku listu xs
. Dakle fmap id
je identička funkcija, pa je zadovoljen prvi zakon funktora. Drugo, kako je
(fmap g . fmap) [x₁, x₂, ... xₙ]
= fmap g (fmap f [x₁, x₂, ... xₙ])
= [g (f x₁), g (f x₂), ... g (f xₙ)]
= fmap (g . f) [x₁, x₂, ... xₙ]
, sledi da je (fmap g . fmap) xs = fmap (g. f) xs
za svaku listu xs
. Prema tome zadovoljen je i drugi zakon.
U slučaju ove instance operator <$
zamenjuje sve vrednosti u listi sa jednom vrednošću:
ghci> True <$ [1,2,3,4,5] [True,True,True,True,True]
<$
nije mnogo zanimljiv. I zaista, retko se javlja potreba za korišćenjem ovog operatora.Sa apstraktnim tipom Maybe :: * -> *
smo motivisali funktore u prethodnoj sekciji. Instanca Functor Maybe
je takođe već definisana u Haskelu:
instance Functor Maybe where fmap _ Nothing = Nothing fmap f (Just a) = Just (f a)
fmap
u potpunosti odgovara definiciji maybeMap
do koje smo sami došli ranije.U kontekstu ove instance, operator <$
zamenjuje vrednost u možda-tipu, ako ta vrednost postoji:
ghci> 2 <$ Just 7 Maybe 2 ghci> 2 <$ Nothing Nothing
Apstraktni tip (,) :: * -> * -> *
ne može biti funktor, jer ne poseduje odgovarajuću vrstu. Ali parcijalnom aplikacijom na neki tip T
dobijamo apstraktni tip (,) T :: * -> *
koji može biti funktor. Upravo je na taj način definisana instanca Functor ((,) a)
za svaki tip a
:
instance Functor ((,) a) where fmap f (x,y) = (x, f y)
Dakle u ovom kontekstu, fmap
primenjuje funkciju na drugu koordinatu uređenog para, a operator <$
zamenjuje drugu koordinatu sa nekom vrednošću:
ghci> fmap (+10) (1, 2) (1, 12) ghci> "Haskel" <$ (True, 2) (True, "Haskel")
Slično su definisane i instance za (,,) a
i (,,,) a b
. Kao i kod uređenih parova, fmap
i <$
utiču samo na poslednju koordinatu.
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
:8:
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
maybeMap2
podiže funkciju od dva argumenta do funkcije koja "radi" sa možda-tipovima.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 kodu9. 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
funkciju10:
maybeApply :: Maybe (a -> b) -> Maybe a -> Maybe b maybeApply (Just f) (Just x) = Just $ f x maybeApply _ _ = Nothing
Nothing
, pa zato i vraćamo 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đe11 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
Nothing
, što nije mnogo korisno.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 gore12. Zanimljivo je da je moguće uraditi i suprotno: definisati funkciju <*>
preko funkcije liftA2
. Ta definicija13 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:
fmap f x = pure f <*> x
.pure id <*> v = v
.u <*> pure y = pure ($ y) <*> u
.pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
.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 funktor14, 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.
Definišimo konkretne vrednosti:
f :: Bool -> String f b = show b g :: FromInt Bool g n = even n
Ako učitamo definicije funkcija (zajedno sa definicijom instance), možemo se uveriti u novi funktor:
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.
Funkcija read :: Read a => String -> a
koja "čita" vrednost iz niske, nije ništa drugo nego jedan parser.
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 funktora15.
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.
- 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 vrednostiT
neće vraćati samo vrednost tipaT
, već uređen par tipa(String, T)
, gde prva koordinata označava ostatak niske koja se parsira. - 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-vrednostMaybe (String, T)
. Ako je parser uspeo, rezultat je oblikaJust (s, x)
za neku niskus
i vrednostx :: T
. U suprotnom, parser vraćaNothing
.
Uzimajući prethodno u obzir, stižemo do definicije tipa
newtype Parser a = P (String -> Maybe (String, a))
Parser Int
, a parser lista logičkih vrednosti je tipa Parser [Bool]
, itd...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
Kreirajmo parser koji parsira jedno slovo iz niske. Taj parser ima tip Parser Char
. Sa konstruktorom P
obuhvatićemo funkciju koja uzima jedno slovo sa početka niske. Ako je niska prazna, parser će vratiti Nothing
.
slovo :: Parser Char slovo = P f where f [] = Nothing f (x:xs) = Just (xs, x)
f
vrši glavnu ulogu. Međutim, da bi dobili vrednost tipa Parse Char
, neophodno je da upakujemo ovu funkciju u konstruktor P
. Naravno, postavlja se pitanje zašto je bilo neophodno da definišemo novi tip a ne tipski sinonim koji koji ne bi zahtevao konstruktor. Razlog tome je što za novi tip možemo definisati instance klasa Functor
i Applicative
, što nije moguće sa tipskim sinonimom koji se odnosi na tip funkcije.Testiranje parsera je veoma jednostavno (i veoma čitljivo!):
ghci> parsiraj slovo "Hello world!" Just ("ello world!", 'H') ghci> parsiraj slovo "" Nothing
Nakon slova, najprirodnije je kreirati parser cifre. Parser cifre treba da nam vrati numeričku vrednost cifre, ako niska koju parsira počinje sa cifrom.
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
Enum
, te je moguće koristiti funkciju fromEnum
koja daje ASCII vrednost karaktera. Oduzimanjem te vrednosti od ASCII vrednosti karaktera '0'
, dobijamo numeričku vrednost koju niska predstavlja.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']
).
Često je zgodno da kreiramo funkciju koja kreira nekakav parser na osnovu prosleđenih argumenata. Parser simbol :: Char -> Parser Char
je primer takve funkcije. Funkcija simbol
uzima jedan karakter i vraća parser koji parsira isključivo taj karakter, a za sve ostale karaktere podbacuje.
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
Definitivno jedan od najkorisnijih parsera je parser celobrojnih vrednosti. Zato, definišimo parser koji sa početka niske parsira broj. Ovaj problem je svakako potrebno rešiti rekurzivno, jer dužina zapisa broja može biti proizvoljno velika.
Strategiju za implementaciju ćemo demonstrirati na jednom primeru. Pretpostavimo da nam je data niska "123aa"
. Cilj je parsirati vrednost 123
. Prvo ćemo pokušati da parsiramo cifru. U našem slučaju, ovaj pokušaj će uspeti, i daće nam 1
, te ćemo stoga pokušati da parsiramo ostatak niske. Međutim, cifra 1
koju smo upravo parsirali može predstavljati različite vrednost (jedan, jednu deseticu, jednu stotinu, itd...). Zbog toga ovu vrednost prosleđujemo rekurzivnom pozivu parsera. U rekurzivnom pozivu pokušaćemo da parsiramo ostatak niske, tj. "23aa"
, što će supeti i dati nam vrednost 2
. Vrednost iz prvog koraka, 1
, pomnožićemo sa 10
i dodati na sledeću vrednost koju parsiramo a to je 2
. Time se dobija vrednost 12
koju prosleđujemo još jednom rekurzivnom pozivu u kom pokušavamo da parsiramo nisku "3aa"
. Kako je i ovo parsiranje uspešno, vrednost koju smo prosledili, 12
, množimo sa 10
i dodajemo na upravo parsiranu vrednost. Time dobijamo 123
koju prosleđujemo rekurzivnom pozivu zajedno sa niskom "aa"
. Sada će pokušaj parsiranja cifre biti neuspešan, što predstavlja znak da se došlo do kraja zapisa broja. Zbog toga, samo ćemo vratiti vrednost koja nam je prosleđena.
Dakle rekurzivna funkcija broj
uzima vrednost x :: Int
koja je do tada parsirana, i vraća Parser Int
koji parsira nisku i konstruiše broj takav da su početne cifre parsiranog broja upravo cifre broja x
. Zvuči komplikovano, ali kôd je sasvim jednostavan:
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'
Funkciju parsiraj
možemo pokrenuti samo nad vrednostima tipa Parser A
. Prema tome, pri inicijalnom pozivu, neophodno je proslediti inicijalnu vrednost acc
funkciji broj
. Naravno, inicijalna vrednost bi trebalo da bude 0
, jer u suprotnom nećemo dobiti broj koji očekujemo:
ghci> parsiraj (broj 0) "123abc" Just ("abc",123)
Navedeni pristup očigledno funkcioniše, ali ima dve mane. Prvo, neophodno je uvek proslediti broj 0
pri inicijalnom pozivu. Drugo, parsiranje će uvek uspeti, čak iako se na početku niske ne nalazi broj (u tom slučaju vrednost koju smo prosledili biće vraćena):
ghci> parsiraj (broj 987) "123ab" Just ("aa",987123) ghci> parsiraj (broj 56) "abc" ("abc", 56)
Zbog opisanih nedostataka, navedenu definiciju "upakovaćemo" u dodatni kod koji predstavlja inicijalno parsiranje cifre. Ako ovo parsiranje ne uspe, vraćamo Nothing
. U suprotnom, pokrećemo prethodno opisani algoritam sa parsiranom cifrom kao inicijalnom vrednošću.
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)
parsiraj p s
je tipa Maybe (A, String)
za neki tip A
. Zbog toga fmap f'
primenjena na ovu vrednost se ponaša u skladu sa funktorom Maybe
, a to je da primenjuje funkciju na vrednost ako ona postoji unutar konstruktora Just
. Vrednost Nothing
se ne menja.Zadatak 7. Dokazati da navedena definicija poštuje dva zakona funktora.
Zadatak 8. Prethodnu definiciju funkcije fmap
jednostavnije zapisati korišćenjem fmap
metoda ostalih funktora.
Lambdu \s -> fmap f' (parsiraj p s)
možemo shvatiti kao primenu funkcije fmap f'
na vrednost koja je dobijena primenom funkcije parsiraj p
na vrednost s
. A to upravo znači da je navedena lambda kompozicija funkcija fmap f'
i parsiraj p
. Međutim ta kompozicija je upravo fmap
u smislu tipa (->) String
, te možemo pisati fmap (fmap f') (parsiraj p)
. Time dobijamo:
instance Functor Parser where fmap f p = P (fmap (fmap f') (parsiraj p)) where f' (x, y) = (x, f y)
Definicija pomoćne funkcije f'
je ništa drugo nego fmap
u smislu uređenih parova, te se možemo osloboditi definicije f'
. Zagrade koje su obuhvatale izraz ispred konstruktora P
možemo zameniti sa operatorom $
, a umesto parsiraj p
možemo parser dekonstruisati sa leve strane jednakosti. Dobijamo izuzetno elegantan kôd:
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.
Od parsera cifra
iz gornjeg primera, kreirajmo parser logičkih vrednosti. Ovaj parser će odrediti da li niska započinje cifrom koja je parna.
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'
primeni
, proverava da li je parsiranje sa p1
uspelo. Ako jeste uspelo, tada se rezultat (s', f)
prosleđuje parseru p2
, tako što se parser fmap f p1
pokreće nad ostatkom 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.
Kreirajmo parser koji parsira jedno slovo, zatim cifru i zatim te dve vrednosti kombinuje u uređeni par. Iz prethodnih primera i zadataka imamo parsere slovo :: Parser Char
i cifra :: Parser Int
, a želimo parser slovoCifra :: Parser (Char, Int)
.
Funkcija f = \x y -> (x, y) :: a -> b -> (a, b)
kombinuje dve vrednosti u uređen par16. Stoga, vrednost pure f :: Parser (a -> b -> (a, b))
je moguće sa operatorom17 <*>
primeniti na dve vrednosti tipa Parser A
i Parser B
, da bi dobili vrednost Parser (A, B)
. I zaista
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.
Definišimo parser decimalanBrojSaTačkom :: Parser Float
koji parsira broj oblika \[\overline{a_1\cdots a_n .b_1\cdots b_n}\] Očigledno, cifre pre i posle decimalne tačke ćemo parsirati sa parserom broj
. Da bi parsirali i tačku, možemo koristiti parser simbol '.'
koji ćemo ukombinovati sa <*
sa parserom koji parsira cifre pre tačke (alternativno, sa *>
i parserom koji parsira cifre nakon decimalne tačke).
ghci> parsiraj (broj <* simbol '.') "123.456" ("456",123)
Na samom kraju, potrebno da dve vrednosti tipa Int
ukombinujemo u jedan broj tako da druga vrednost predstavlja razvoj nakon decimalne tačke, tj. potrebno nam je preslikavanje \[\left(\overline{a_1\cdots a_n}, \overline{b_1\cdots b_n}\right) \mapsto \overline{a_1\cdots a_n .b_1\cdots b_n}\] Prvo, obe koordinate ćemo transformisati u Double
vrednosti sa fromIntegral
funkcijom. Drugu koordinatu, \(y\), možemo rekurzivno deliti sa \(10\) dokle god je veća od \(1\), da bismo dobili deo nakon decimalne tačke.
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)
Imitirajući ideju o rekurzivnoj primeni parsera, možemo na jednostavan način implementirati funkciju niska :: String -> Parser String
koju smo spomenuli u prethodnom zadatku.
Prvo, parsiranje prazne niske iz bilo koje druge niske uvek treba da uspe. Ovo predstavlja bazni slučaj. Drugo, parsiranje neke niske x:xs
iz niske s
može da se izvede tako što se prvo parsira simbol x
, pa ako to parsiranje uspe, rekurzivno se parsira i ostatak xs
:
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
Koristeći kombinator ili
možemo lako napraviti parser koji parsira jednu od dve logičke vrednosti:
ghci> logičkaVrednost = niska "True" `ili` niska "False" ghci> parsiraj logičkaVrednot "True" Just ("","True") ghci> parsiraj logičkaVrednot "False" Just ("","False")
ili
je veoma zgodno postaviti u infiksni oblik kako je prikazno u prvoj liniji. Iako možda deluje neobičnao, ovakva sintasa doprinosi čitljivosti jer zapis podeća na prirodne rečenice: parsirati nisku "True" ili nisku "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 ]"
.