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) parametra 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 parametra, ali ne rešava problem sa funkcijama tri i više parametara. 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 parametara 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 deklaraciji klase, je klasno ograničenje Functor f => Applicative f kojim se zahteva da sve instance klase Applicative budu instance i klase Functor. Nakon deklaracija 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.

Liste kao aplikativni funktori

Da bi [] :: * -> * postao 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. Posmatrajući samo tipove navedenih funkcija, možemo dati mnogo različitih definicija funkcija. Naravno neće sve definicije biti dovoljno dobre, tako da zakoni aplikativnih funktora budu zadovoljeni. Ali, u slučaju lista postoji više mogućih definicija instance Applicative [a] koje zadovoljavaju pomenute zakone. Igrom slučaja, jedna od tih definicija je odabrana i implementirana u prelidu. Tu definiciju ćemo prikazati u nastavku:

Funkcija pure uzima vrednost nekog 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... Heuristički govoreći, konstantna funkcija \x -> [] bi bila beskorisna, dok bi funkcije poput \x -> [x, x], \x -> [x, x, x] vraćale "previš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)¹⁴. Zbog toga, <*> definišemo kao operaciju koja primenjuje svaku funkciju iz leve liste na svaku vrednost iz desne: fs <*> xs = [ f x | f <- fs, x <- xs ]. Za ovako definisane pure i <*>, nije teško dokazati zakone aplikativnih funktora.

Strelice kao funktori

Još od prvih lekcija, koristili smo konstruktor ->, takozvanu strelicu, za konstrukciju tipa funkcija. U lekciji o vrstama, uverili smo se da je strelica binarni tipski konstruktor.

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