Funktori
Koncepti funktora i monade su važni za Haskel. Iako se mnogi programi (ali ne svi!) mogu zapisati bez korišćenja navedenih konecpata, korišćenje funktora i monada značajno olakšava pisanje (i čitanje) koda.
Funktor i monada su preuzeti iz apstraktnih oblasti matematike, ali se u Haskelu ovi koncepti svode na klase tipova. Pre nego što tačno definišemo nove pojmove, pokušaćemo da damo motivaciju.
Funktori
Motivacija
U jednoj od prethodnih lekcija, obradili smo Maybe :: * -> *
apstraktni tip. Kao što smo videli, Maybe A
je tip koji osim vrednosti tipa A
sadrži i vrednost Nothing
koja predstavlja odsustvo vrednosti.
Zamislimo 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, ilustarcije 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 unifroman način to radi za nas.
Kada radimo sa više funkcija, tada maybeMap
možemo da iskoristimo sa operatorm 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 zanmljivu 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 tipа A
prave tip strukture koje sadrže vrednosti (ili vrednost) tipa A
6. Ogovarajć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
funckije. 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.
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 apstrakti 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 kordinatu 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 opereator 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 implemenitrati 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 korisitmo 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 definsiati 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 operaor 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 definija 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 fukcija koja će vršiti kompoziciju. Napomenimo, da je <*>
definsian 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
.
Liste kao aplikativni funktori
Da bi [] :: * -> *
postato Aplikativni funktor, potrebno je samo definisati funkciju pure :: a -> [a]
i jednu od funkcija (<*>) :: [a -> b] -> [a] -> [b]
ili liftA2 :: [a -> b -> c] -> [a] -> [b] -> c
. Posmatajući samo tipove navedenih funkcija, možemo dati mnogo različitih definicija funkcija. Međutim, ako se osvrnemo na četiri gorenevedena zakona, uvidećemo da dolazimo do jedinstvih definicija.
Funkciju pure
uzima vrednost nekon neodređenog tipa a
i vraća vrednost tipa [a]
. Kako je tip u potpunosti neodređen (nije ograničen nekom tipskom klasom), ne možemo mnogo što šta uraditi sa vrednošću. Za vrednost x
, funkcija pure
može vratiti []
, [x]
, [x, x]
, [x, x, x]
, itd... Konstantna funkcija \x -> []
bi bila beskorisna, dok bi funkcije poput \x -> [x, x]
, \x -> [x, x, x]
vraćale prviše. Zbog toga, definisaćemo pure
kao funkciju \x -> [x]
.
Da bismo definisali <*>
neophodno je da obratimo pažnju na zakone aplikativnih funktora. Prvo, iz fmap f x = pure f <*> x
, i iz pure f = [f]
sledi da [f] <*> [x1,...,xn]
mora biti [f x1,...,f xn]
. Prema tome, <*>
primenjuje funkcije iz leve liste na vrednosti iz desne liste. Postoji mnogo načina na koje se takva primena može definisati, i za sada nam nije jasno kako se više funkcija primenjuje na više vrednosti (za sada samo razumemo [f] <*> xs
)14. Zbog toga, <*>
definišemo kao operaciju koja primenjuje svaku funkciju iz leve liste na svaku vrednost iz desne.