Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

PROGRAMIRANJE U HASKELLU

Ak.god. 2011/12.

LEKCIJA 15: Monade 2

v1.0

(c) 2011 Jan Šnajder

==============================================================================

> import Data.List
> import Control.Monad
> import Data.Maybe
> import System.Random

== MONADA STANJA =============================================================

Haskell je čisto funkcijski jezik i nedopušta popratne efekte. To znači da u
Haskellu nemamo implicitnog stanja, odnosno izračuni u Haskellu su "bez stanja"
(engl. stateless computation). Ako ipak želimo raditi sa stanjem, moramo ga
eksplicitno vući naokolo po funkcijama. Taj problem možemo riješiti uporabom
monade stanja, koja "skriva" eksplicitno stanje unutar monade. To nam efektivno
omogućava izračun sa stanjem (engl. stateful computation). IO-monada je zapravo
monada stanja.

Razmotrimo najprije dva primjera u kojima koristimo eksplicitno stanje.

Primjer 1: Označavanje čvorova stabla

> data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show,Eq)

> t1 = Branch (Branch (Leaf 'b') (Leaf 'c')) (Branch (Leaf 'd') (Leaf 'a'))

> label :: Tree a -> Tree Int
> label = snd . step 0
>   where step n (Leaf _) = (n+1, Leaf n)
>         step n (Branch t1 t2) = let
>           (n1,t1') = step n t1
>           (n2,t2') = step n1 t2
>           in (n2,Branch t1' t2') 

Primjer 2: Generator slučajnih brojeva

> g = mkStdGen 13
> (r1,g2) = random g :: (Int, StdGen)
> (r2,g3) = random g2 :: (Int, StdGen)
> (r3,g4) = random g3 :: (Int, StdGen)

U oba gornja slučaja stanje eksplicitno provlačimo kroz sve funkcije: svaka
funkcija kao argument uzima trenutno stanje, a vraća svoju povratnu vrijednost
i izmijenjeno stanje. To možemo lijepo apstrahirati monadom stanja (engl. state
monad). Njezin tip je:

> data SM s a = SM (s -> (s,a))

Monada stanja je dakle *funkcija* koja uzima stanje i vraća novo stanje i
povratnu vrijednost. Slijed izračuna sa stanjem dobit ćemo ako povežemo
više takvih funkcija u jednu funkciju, koju ćemo zatim primijeniti na početno
stanje.

Definirajmo instancu razreda 'Monad':

> instance Monad (SM s) where
> 
>   return a = SM (\s -> (s,a)) 
>   
>   SM sm0 >>= fsm1 = SM $ \s0 ->
>     let (s1,a1) = sm0 s0     -- lijevi izračun nad stanjem
>         SM sm1 = fsm1 a1     -- izračun "desne monade"
>         (s2,a2) = sm1 s1     -- desni izračun nad stanjem
>     in (s2,a2)

'return a' vraća funkciju koja uzima stanje i vraća nepromijenjeno stanje i
vrijednost 'a'. Definicija za operator povezivanja (>>=) je nešto složenija.
Treba se prisjetiti tipa tog operatora:

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

Treba otpakirati lijevu vrijednost 'm a' i predati je funkciji 'a -> m b'. U
slučaju monade stanja, zapakirane vrijednosti su i same funkcije.

Primjer:

> inc :: SM Int ()
> inc = SM (\s -> (s+1,()))

> dec :: SM Int ()
> dec = SM (\s -> (s-1,()))

> foo :: SM Int ()
> foo = inc >> inc >> inc

Kako pokrenuti? Treba nam funkcija koja "izvodi monadu". Konkretno, funkcija
uzima tip 'SM' i početno stanje, opakirava funkciju iz monade i primjenjuje je
na zadano stanje.

> runSM' :: SM s a -> s -> (s,a)
> runSM' (SM sm0) s0 = sm0 s0     -- može li kraće?

Isprobajmo:

> v1 = runSM' foo 10
> v2 = runSM' (dec >> inc >> dec) 0

Dakle, monadu stanja možemo shvatiti i kao zapis slijeda izračuna koji čekaju
da budu izvršeni. Uporabom operatora (>>=) povezujemo izračune u jedan veći
niz. Taj niz je zapravo jedna velika funkcija koju treba primijeniti na početno
stanje. Kada dakle taj niz izračuna želimo izvršiti, koristimo funkciju 'runSM'
koja otpakirava funckiju i primjenjuje je na početno stanje.

U većini slučajeva nam treba samo povratna vrijednost izračana, a ne i konačno
stanje. Možemo definirati:

> runSM :: SM s a -> s -> a
> runSM (SM sm0) = snd . sm0

Isprobajmo:

> v3 = runSM foo 10

Naravno, povratna vrijednost je (), jer smo mijenjali samo stanje, a njega sad
više ne vraćamo. Moramo nekako stanje prebaciti u povratnu vrijednost. To je
lako:

> get :: SM s s
> get = SM (\s -> (s,s))

> v4 = runSM (foo >> get) 10

Kako bismo definirali funkciju 'set' ? Što je njezin tip?

> set :: s -> SM s ()
> set a = SM (\_ -> (a,()))

> v5 = runSM (set 5) 10
> v6 = runSM (set 5 >> get) 10
> v7 = runSM (set 5 >> inc >> get) 10

Što daju sljedeći izračuni?

> v8 = runSM (get >>= set) 10
> v9 = runSM (get >>= set >> get) 10
> v10 = runSM (return 0 >> inc >> get) 10
> v11 = runSM (get >> return 5) 10
> v12 = runSM (inc >> return 0) 10
> v13 = runSM (dec >> return 0 >> get) 10
> v14 = runSM (get >>= set . (+5) >> get) 10

Izračun sa stanjem je mnogo pregledniji ako se koristi do-notacija. Npr. za
zadnji primjer:

> foo2 :: SM Int Int
> foo2 = do
>   x <- get
>   set (x+5)
>   get

> v15 = runSM foo2 7

Što radi sljedeća funkcija i kojeg je tipa?

> foo3 = do
>   x <- get
>   set (x+100)
>   return ()

Napišimo sada funkciju za označavanje čvorova stabla.

> label2 :: Tree a -> SM Int (Tree Int)
> label2 (Leaf _) = do 
>   n <- get
>   set (n+1)
>   return (Leaf n)
> label2 (Branch t1 t2) = do
>   t1' <- label2 t1
>   t2' <- label2 t2
>   return $ Branch t1' t2'

> labelTree :: Tree a -> Tree Int
> labelTree t = runSM (label2 t) 0

== VJEŽBA 1 ==================================================================

Rješite sljedeće zadatke unutar monade stanja 'SM s a'.

1.1.
- Napišite sljedeće funkcije:
    nop :: SM s ()
    reset :: SM Int ()
    update :: (s -> s) -> SM s ()
  Svaku ovu funkciju napišite na tri načina: (1) izravno nad tipom 'SM', (2)
  monadički bez do-notacije i (3) monadički u do-notaciji.

1.2.
- Napišite funkciju
    random' :: (RandomGen g, Random a) => SM g a
  za generiranje slučajnog broja sa slučajnim generatorom 'g' kao stanjem.
  Funkcija interno treba koristiti funkciju 'random'.
- Napišite funkciju
    initRandom :: Int -> SM StdGen ()
  koja inicijalizira generator zadanom sjemenskom vrijednošću.
- Napišite funkciju
    threeRandoms :: SM g (Int,Int,Int)
  koja vraća tri slučajna broja.

== LISTA KAO MONADA ==========================================================

Lista (odnosno tipski konstruktor '[]') također je instanca monade, definirana
ovako:

  instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    fail _ = []

Operator (>>=) mapira funkciju 'f' na svaki element lijeve liste, što rezultira
listo listi, i zatim se te liste povezuju u jednu listu. Npr.:

> l1 = [1,2,3] >>= \x -> [x,x^2]

ili

> l2 = do
>   x <- [1,2,3]
>   [x,x^2]

Što daje ovo?

> l3 = [1,2,3] >> [4,5,6]

To je isto kao:

> l3' = [1,2,3] >>= \_ -> [4,5,6]

Drugačiji primjer:

> tuples = do
>   n <- [1..10]
>   c <- "abc"
>   return (n,c)

U ovom primjeru gradimo listu dvojki (kartezijev produkt [1..1]*"abc"). Isto
smo mogli napraviti s pomoću sažetog zapisa liste:

> tuples' = [(n,c) | n <- [1..10], c <- "abc"]

Zapravo, sažet zapis liste samo je sintaktički šećer za listu kao monadu.

Što radi sljedeća funkcija?

> fooo [] = [[]]
> fooo xs = do
>   x <- xs
>   ys <- fooo (delete x xs)
>   return (x:ys)

== FUNKCIJE ZA RAD S MONADAMA ================================================

U kontekstu IO-monade već smo upoznali neke korisne funkcije višeg reda za rad
s monadama iz modula 'Control.Monad':

sequence :: Monad m => [m a] -> m [a]
sequence_ :: Monad m => [m a] -> m ()
replicateM :: Monad m => Int -> m a -> m [a]
replicateM_ :: Monad m => Int -> m a -> m ()
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
foldM_ :: Monad m => (a -> b -> m a) -> a -> [b] -> m ()
forM :: Monad m => [a] -> (a -> m b) -> m [b]
forM_ :: Monad m => [a] -> (a -> m b) -> m ()
forever :: Monad m => m a -> m b

Sve ove funkcije primjenjive su naravno na bilo koji tip iz razreda 'Monad',
premda nisu uvijek jednako korisne za svaki tip.

Funkcija 'sequence' evaluira svaku monadu u listi monada, rezultate skuplja u
listu i pakira ih u monadu.

sequence [] = return []
sequence (m:ms) = do
    x <- m
    xs <- sequence ms
    return (x:xs)

Npr.:

> e1 = sequence [Nothing,Just 1,Just 2]
> e2 = sequence [Just 1,Just 2,Nothing]
> e3 = sequence [Just 1,Just 2,Just 3]

> inc3 = sequence_ [inc,inc,inc]
> e4 = runSM (inc3 >> get) 3

> e5 = sequence [[1,2,3],[4,5,6]]

To je ekvivalentno s:

  do x <- [1,2,3]
     y <- [4,5,6]
     return [x,y]

> e6 = replicateM 10 (Just 1)

> f x = if even x then Just x else Nothing
> e7 = forM [1,2,3] f

> inc30 = replicateM_ 10 inc3

> e8 = runSM (inc30 >> dec >> get) 0

U nastavku razmatramo još neke korisne funkcije.

Funkcija

  (=<<) :: Monad m => (a -> m b) -> m a -> m b

je ista kao i operator povezivanja (>>=), samo ima zamijenjen ("flipan")
poredak argumenata. Možemo je koristiti ako želimo da se obrada izvodi zdesna
nalijevo, kao što je to slučaj s kompozicijom u čistom funkcijskom kodu. Ovo
ima smisla ako kombiniramo čist kod i monadički kod. Npr.:

> main5 = 
>   putStr . unlines . filter (not . null) . lines =<< getContents

Funkcija 

  join :: Monad m => m (m a) -> m a

eliminira jednu razinu gniježđenja monade. Ako monadički tip zamislimo kao
kutiju koja pohranjuje podatke, onda je 'm (m a)' kutija u kutiji koja sadržava
podatke tipa 'a'. Pomoću funkcije 'join' izvadit ćemo te podatke i smjestiti ih
u jednu kutiju.

Npr. 

> e9 = join (Just (Just 5))
> e10 = join $ return getLine

Definicija funkcije 'join' je jednostavna:

  join :: (Monad m) => m (m a) -> m a
  join m =  m >>= id

Ova funkcija je više teorijski zanimljiva jer nam omogućava alternativnu
definiciju monade. Pretpostavimo da je 'm' instanca razreda 'Functor', pa da
ima definiranu funkciju 'fmap':

  fmap :: Functor f => (a -> b) -> f a -> f b

Umjesto da za 'm' definiramo operator povezivanja (>>=), možemo definirati
funkciju 'join'. Operator (>>=) onda je definiran kao:

  (>>=) :: (Functor m, Monad m) => m a -> (a -> m b) -> m b
  m >>= k = join $ fmap k m

Tj., umjesto da otpakiramo vrijednost 'm a', primjenimo na nju funkciju 
'a -> m b' i dobijemo 'm b', možemo unutar 'm a' primijeniti funkciju 
'a -> m b', dobiti 'm (m b)' i zatim "spljoštiti" na 'm b'.

Npr.:

  Just 5 >>= \x -> Just (x + 1)
  => join (fmap (\x -> Just (x + 1)) (Just 5))
  => join (Just ((\x -> Just (x+1)) 5))
  => join (Just (Just 6))
  => Just 6 

Međutim, kao što vidjeli, u Haskellu operator (>>=) nije definiran preko
'join'. Kada bi to bio slučaj, svaka instanca monade morala bi biti i instanca
funktora (a to doista jest tako u teoriji kategorija).
Više:
http://en.wikibooks.org/wiki/Haskell/Category_theory#Monads

Jedna vrlo korisna funkcija je 'liftM':

  liftM :: Monad m => (a -> b) -> m a -> m b
  liftM f m = m >>= \x -> return (f x)

ili 

  liftM f xs = xs >>= (return . f)

Funkcija otpakirava vrijednost iz monade, primjenjuje funkciju 'a -> b', i
zatim zapakirava vrijednost nazad u monadu. Kažemo da funkcija "podiže" običnu
(čistu) funkciju u monadu, odnosno da funkcija radi izračun unutar monade.

Npr.

> e11 = liftM (+1) (Just 5)

> e12 = liftM (unlines . filter (not . null) . lines) getContents

> e13 = liftM signum [1,2,3]

Vidimo da je funkcija 'liftM' zapravo ista kao i funkcija 'fmap' (koja je pak
za liste ista kao i 'map'). Razlika između 'liftM' i 'fmap' je u tome što je
prva funkcija definirana za instance razreda 'Monad', a druga funkcija za
instance razreda 'Functor'.

Funkciju 'liftM' često koristimo u IO-monadi kada neku čistu funkciju želimo
ugurati da se izvede na rezultatu IO-akcije. Npr.

> catZipped :: FilePath -> FilePath -> IO ()
> catZipped f1 f2 = do
>   xs <- lines `liftM` readFile f1
>   ys <- lines `liftM` readFile f2
>   putStr . unlines $ zipWith (++) xs ys

Postoji i binarna varijanta funkcije 'liftM':

  liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c
  liftM2 f m1 m2 =
      m1 >>= \a ->
      m2 >>= \b ->
      return (f a b)

ili

  liftM2 f m1 m2 = do
    a <- m1
    b <- m2
    return $ f a b

Npr.:

> e14 = liftM2 (+) (Just 2) (Just 3)
> e15 = liftM2 (+) (Just 2) Nothing

> e16 = liftM2 (+) [1,2,3] [4,5,6]

Primjer uporabe 'liftM2' u monadi 'Maybe': evaluacija aritmetičkog izraza.

> data Expr = 
>     Val Double
>   | Add Expr Expr
>   | Sub Expr Expr
>   | Mul Expr Expr
>   | Div Expr Expr
>   deriving (Show,Eq)

> ex = (Val 3) `Add` ((Val 5) `Div` (Val 0))

> eval :: Expr -> Maybe Double
> eval (Val v)     = Just v
> eval (Add e1 e2) = liftM2 (+) (eval e1) (eval e2)
> eval (Sub e1 e2) = liftM2 (-) (eval e1) (eval e2)
> eval (Mul e1 e2) = liftM2 (*) (eval e1) (eval e2)
> eval (Div e1 e2) = case eval e2 of
>   Just 0 -> Nothing
>   e      -> liftM2 (/) (eval e1) e