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¹. 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 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 vrednost³.

Funkcija maybeMap ima još jednu zanmljivu 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 tipа A prave tip strukture koje sadrže vrednosti (ili vrednost) tipa A⁶. 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 * -> *⁷.

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

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 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:⁸:

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 implemenitrati 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 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đ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 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 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 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)¹⁴. Zbog toga, <*> definišemo kao operaciju koja primenjuje svaku funkciju iz leve liste na svaku vrednost iz desne.