Vaje: monade

Osnovna ideja funktorjev in monad je, da lahko "golo" oziroma čisto vrednost zapakiramo v kontejner oziroma ji dodamo kontekst, ki določa, kako s to vrednostjo računamo.

• Tip Maybe vrednosti doda kontekst, ki pove, če vrednost obstaja (Just 42) ali ne (Nothing).
• Seznam je zbirka vrednosti: funkcija, ki vrne seznam, lahko vrne nič, eno ali mnogo vrednosti.

V Haskellu lahko iz nekega tipa naredimo monado tako, da zanj implementiramo določene operacije. Tu si bomo ogledali monadi Input in Output, ki čistim vrednostim dodata kanal za branje oziroma pisanje.

Monada Output

Izhod (angl. output) je računski učinek, ki omogoča pošiljanje podatkov na izhodni kanal (datoteka, zaslon, printer). Izhod lahko uporabljamo tudi v programu kot "akumulator", v katerega dodajamo rezultate z operacijo write.

Podatkovni tip, ki predstavlja to idejo je

data Output o a = Out { result :: a, output :: o }
                  deriving Show

Tip Output o a je zapis s poljem result tipa a in poljem output tipa o, ki predstavljata rezultat nekega izračuna in pripadajoč izhod. Vrednost tega tipa ustvarimo s konstruktorjem Out:

Out 42 "foo"
=> Out {result = 42, output = "foo"}

Tu smo izpis predstavili z nizom. Če želimo tip Output uporabljati kot monado, moramo zanj implementirati določene operacije. Te so definirane z razredi tipov (angl. typeclasses) Functor, Applicative in Monad.

Naloga: write

Definirajte funkcijo write, ki sprejme niz x in ga "izpiše" tako, da vrne zapis tipa Output. Rezultat naj bo enota (), izhod pa kar x. Primer:

write "foo"
=> Out {output = "foo", result = ()}

write [42]
=> Out {output = [42], result = ()}

Functor (Output o)

Razred tipov Functor izgleda tako:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Če želimo, da je tip f (v našem primeru bo to Output o) funktor, moramo implementirati funkcijo fmap. Ta uporabi funkcijo, ki slika iz a v b, da preslika funktor z vsebino tipa a v funktor z vsebino tipa b. Lahko bi rekli tudi, da fmap uporabi funkcijo, ki slika iz a v b za to, da preslika a s kontekstom (izhodom) v b s kontekstom (izhodom), ozirma zapakiran a v zapakiran b.

instance Functor (Output o) where
    -- fmap :: (a -> b) -> Output o a -> Output o b
    fmap f (Out x o) = Out (f x) o

Applicative (Output o)

Razred tipov Applicative definira funkcijo pure in operator <*>:

pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

Funkcija pure vzame navadno vrednost in iz nje zgradi vrednost našega tipa. Pri definiciji si pomagamo z omejitvijo Monoid o, ki določa, da mora tip o vsebovati prazno vrednost mempty (npr. prazen niz ali seznam) in funkcijo mappend, ki združi dve vrednosti v novo vrednost (npr. stakne dva niza ali seznama).

instance Monoid o => Applicative (Output o) where
    -- pure :: a -> Output o a
    pure x = Out x mempty

Definirati moramo še operator <*>, ki pove, kako evalviramo funkcijo z dodanim izhodom na argumentu z dodanim izhodom.

-- (<*>) :: Output o (a -> b) -> (Output o a) -> Output o b
Out f o <*> Out x o' = Out (f x) (mappend o o')

Monad (Output o)

Monada je Applicative, ki vsebuje še funkcijo return in operator >>=:

return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b

Funkcije return nam ni treba definirati, saj dela isto kot pure. Operator >>= pa sprejme a z izhodom in funkcijo, ki iz a slika v b z izhodom, ter vrne b z izhodom. Implementiramo jo tako, da odpakiramo prvi argument in na njem poženemo podano funkcijo:

instance Monoid o => Monad (Output o) where
    -- (>>=) :: Output o a -> (a -> Output o b) -> Output o b
    Out x o >>= f = let (Out y o') = f x in Out y (mappend o o')

Uporaba

Z definirano monado Output lahko med računanjem vrednosti pišemo na izhodni kanal:

primer = do write "Hello,"
            x <- return 10
            write " world"
            y <- return (x + 20)
            write "!"
            return (x * y)
output primer
=> "Hello, world!"

Naloga: isPrime

Definirajte funkcijo isPrime, ki preveri, ali je dano število praštevilo. Namig: pomagate si lahko s funkcijo all p s, ki vrne True natanko tedaj, ko predikat p vrne True za vse elemente seznama s. Primer:

all (>2) [3,4,5]
=> True

S pomočjo funkcije isPrime in monade Output lahko "izpišemo" seznam praštevil med 1 in n:

primes :: Int -> [Int]
primes n = output (loop 2)
    where loop k | k >= n     = return ()
                 | otherwise  = do if isPrime k then write [k] else return ()
                                   loop (k + 1)

Monada Input

Vhod (angl. input) je računski učinek, ki omogoča branje podatkov z vhodnega kanala (datoteka, tipkovnica, povezava TCP, …). Vhodni kanal bomo implementirali s seznamom vrednosti, iz katerega ob vsakem branju odstranimo in vrnemo prvi element.

Uporabili bomo podatkovni tip Input, ki predstavlja izračun, ki je (lahko) odvisen od vhoda:

data Input i a = In { run :: [i] -> (a, [i]) }

Tip Input je zapis z enim samim poljem – funkcijo run, ki sprejme vhod (seznam vrednosti tipa i) in vrne rezultat tipa a ter preostanek vhoda (če nismo prebrali nobenega podatka, vrne kar originalni vhod). Definirajmo consume, ki prebere prvo vrednost z vhoda in jo vrne skupaj s preostankom vhoda:

consume :: Input i i
consume = In { run = (\input -> (head input, tail input)) }

Opomba. Ko definiramo vrednost nekega zapisa, nam polj ni treba poimenovati, ampak jih lahko kar naštejemo:

consume = In (\input -> (head input, tail input))

Sam consume ni funkcija, ampak vrednost tipa Input, ki vsebuje funkcijo v polju run. Uporabimo jo tako:

run consume ["a", "b", "c"]  -- (run consume) nam vrne polje run iz zapisa consume
=> ("a",["b","c"])

Če želimo tip Input uporabljati kot monado, moramo zanj implementirati določene operacije. Te so definirane z razredi tipov (angl. typeclasses) Functor, Applicative in Monad.

Functor (Input i)

Za tip Input i definirajmo funkcijo fmap:

instance Functor (Input i) where
    fmap f (In xrun) = In (\input -> let (x, input') = xrun input in (f x, input'))

To nas spomni na implementacijo map za tokove v OCaml. Funkcija fmap sama ne izračuna ničesar, temveč le definira funkcijo run, ki bo (kasneje) na danem vhodu input pognala xrun, da dobi dejansko vrednost x in nov vhod input', nato pa evalvirala funkcijo f na x ter vrnila (f x, input').

Vse operacije, ki vrnejo vrednost tipa Input, definiramo na ta način – vrednosti tega tipa vsebujejo funkcijo run, ki jo šele kasneje evalviramo na dejanskem vhodu.

Applicative (Input i)

Razred tipov Applicative definira funkcijo pure in operator <*>:

pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

Funkcija pure vzame navadno vrednost in iz nje zgradi vrednost našega tipa tako. Vrednost tipa Input zgradimo tako, da definiramo funkcijo run, ki pri danem vhodu vrne vrednost in nespremenjen vhod:

instance Applicative (Input i) where
    pure x = In (\input -> (x, input))

Operator <*> je podoben fmap, le da je tudi funkcija a -> b zapakirana v funktor f. Zato run najprej poženemo na prvem in nato še na drugem argumentu operatorja <*>. Pri obeh korakih se lahko spremeni tudi vhod:

(In frun) <*> (In xrun) = In (\input -> let (f, input') = frun input
                                            (x, input'') = xrun input'
                                        in (f x, input''))

Monad (Input i)

Na koncu definirajmo še operator >>= (bind), ki sprejme vrednost tipa a (odvisen od vhoda) in funkcijo, ki iz a slika v b (odvisen od vhoda).

instance Monad (Input i) where
    (In arun) >>= f = In (\input -> let (a, input') = arun input
                                    in run (f a) input')

Uporaba

Oglejmo si primer uporabe monade Input:

primer = do x <- consume
            y <- consume
            return ("First input: " ++ x ++ "  Second input: " ++ y)

Vrednost primer je monada Input, ki prebere dva niza z vhoda in vrne sestavljen niz. Poženemo jo tako kot consume:

run primer ["prvi niz", "drugi niz", "preostanek"]
=> ("First input: prvi niz  Second input: drugi niz",["preostanek"])

Kaj se zgodi, če v vhodnem kanalu ni dovolj podatkov?

Kombiniran vhod/izhod

Ko imamo monadi za vhodni in izhodni kanal, bi ju želeli tudi kombinirati:

do write "What is your name? "
   name <- consume
   write "Hello, " ++ name

Tega v Haskellu ne moremo narediti brez dodatnega dela (lahko pa uporabimo vgrajeno monado IO, ki podpira vhod in izhod). Na predavanjih boste spoznali jezik Eff, ki računske učinke obravnava drugače.