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

PROGRAMIRANJE U HASKELLU

Ak.god. 2011/12.

LEKCIJA 14: Monade 1

v1.0

(c) 2011 Jan Šnajder

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

> import Data.List
> import Data.Char
> import Control.Monad
> import Data.Maybe

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

Monade su vrlo važan koncept u Haskellu. Monade apstrahiraju različite načine
izračuna: izračun sa stanjem, nedeterministički izračun, izračun koji može ne
uspjeti i sl. Jedan primjer monade je IO-monada, pomoću koje se izvode
sve ulazno-izlazne operacije.

Uporabu monade motivirat ćemo jednostavnim primjerom. Prisjetimo se
(rekurzivne) podatkovne strukture:

> data Sex = Male | Female deriving (Show,Read,Eq,Ord)
> data Person = Person {
>   forename :: String,
>   surname  :: String,
>   sex      :: Sex,
>   mother   :: Maybe Person,
>   father   :: Maybe Person,
>   partner  :: Maybe Person,
>   children :: [Person] } deriving (Show,Read,Eq,Ord)

Neka je definirano:

> pero  = Person "Pero" "Perić" Male    (Just ana) Nothing Nothing    []
> ana   = Person "Ana"  "Anić"  Female  (Just tea) Nothing Nothing    [pero]
> tea   = Person "Tea"  "Teić"  Female  Nothing    Nothing (Just ivo) [ana]
> ivo   = Person "Ivo"  "Ivić"  Male    Nothing    Nothing (Just tea) [ana]

Razmotrimo dvije funkcije:

> grandmothersPartner :: Person -> Maybe Person
> grandmothersPartner p = case mother p of
>   Just m -> case mother m of
>     Just g  -> partner g
>     Nothing -> Nothing
>   Nothing -> Nothing

> partnersForename :: Person -> Maybe String
> partnersForename p = case partner p of
>   Just p  -> Just $ forename p
>   Nothing -> Nothing

Kod obje se funkcije javlja isti problem: izračunava se neki izraz koji može
biti 'Nothing' ili 'Just x'. U prvom slučaju izračun treba vratiti 'Nothing', a
u drugom slučaju na 'x' treba primijeniti neku drugu funkciju. Ta druga
funkcija ili opet vraća tip 'Maybe', ili vraća neki drugi tip koji je potrebno
zapakirati u 'Just'. Problem je u tome što stalno moramo otpakiravati i
zapakiravati vrijednosti podatka zapakiranog u tipu 'Maybe'. To rezultira
ružnim kodom.

U ovim primjerima zapravo se bavimo izračunima koji mogu ne uspjeti. Ako
izračun ne uspije, vraća 'Nothing', inače vraća 'Just x'.  Nakon toga slijedi
novi izračun nad 'x', koji opet može ne uspjeti, itd. Trebamo uvesti neku
apstrakciju koja će ovo pojednostaviti.

Kod možemo pojednostaviti tako da uvedemo dvije funkcije:

> inject :: a -> Maybe a
> inject x = Just x    -- ili: inject = Just

Funkcija 'inject' samo "zapakirava" vrijednost u tip 'Just'. (Funkcija je
identična kao 'Just', ali uvodimo je iz didaktičkog razloga.)

> bind :: Maybe a -> (a -> Maybe b) -> Maybe b
> bind Nothing _  = Nothing
> bind (Just x) k = k x

Dakle, 'bind' povezuje neku vrijednost zapakiranu u Maybe-tip s funkcijom koja
uzima tu zapakiranu vrijednost i vraća novu vrijednost Maybe tipa. Ako prva
"akcija" zakaže i vrati Nothing, priča se odmah prekida. Inače otpakiravamo
vrijednost i primjenjujemo na nju funkciju 'f'.

Sada možemo pisati:

> grandmothersPartner2 :: Person -> Maybe Person
> grandmothersPartner2 p = (mother p `bind` mother) `bind` partner

> partnersForename2 :: Person -> Maybe String
> partnersForename2 p = partner p `bind` (\r -> inject (forename r))

ili kraće:

> partnersForename2' :: Person -> Maybe String
> partnersForename2' p = partner p `bind` (inject . forename)

Operacije koje smo upravo definirali zapravo definiraju MONADU.

Monada je tipski razred svih polimorfnih tipova koji podržavaju operacije
POVEZIVANJA (bind) i operaciju INJEKTIRANJA u tip. Operacija povezivanja
definirana je kao operator (>>=), a operacija injektiranja kao funkcija
'return'. Definicija razreda "Monad' je sljedeća:

  class Monad m where
      (>>=)       :: m a -> (a -> m b) -> m b
      return      :: a -> m a

Primijetite da je 'm' tipski konstruktor vrste '* -> *'. Npr. to može biti
tipski konstruktor 'Maybe', '[]', 'IO', ili neki korisnički definiran
konstruktor.

Instanca razreda 'Monad' za tipski konstruktor 'Maybe' definirana je u
'Data.Maybe', i to upravo onako kako smo je mi definirali:

  instance  Monad Maybe where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing
    
    return              = Just

Sad možemo pisati:

> grandmothersPartner3 :: Person -> Maybe Person
> grandmothersPartner3 p = (mother p >>= mother) >>= partner

> partnersForename3 :: Person -> Maybe String
> partnersForename3 p = partner p >>= return . forename

Zapravo, razred 'Monad' ima još dodatne dvije funkcije:

  class Monad m where
      (>>=)       :: m a -> (a -> m b) -> m b
      (>>)        :: m a -> m b -> m b
      return      :: a -> m a
      fail        :: String -> m a

Najmanja potpuna definicija jest definicija za funkcije (>>=) i 'return', dakle
ove dvije dodatne funkcije nije potrebno definirati. Njihova podrazumjevana
definicija je:

  m >> k = m >>= \_ -> k
  fail = error

Operator (>>) je sličan operatoru povezivanja (>>=), ali zdesna ne uzima akciju
tipa 'a -> m b', nego akciju 'm b', tj. akcija zdesna ne ovisi o rezultatu
akcije slijeva. Možemo reći da operator (>>) ne prosjeđuje rezultat prve akcije
drugoj akciji. Operator (>>) naziva se operator NIZANJA (sequencing).

Npr.

> foo :: Person -> Maybe Person
> foo p = partner p >> mother p 

Operator (>>) će nam biti koristan kod IO operacija tipa 'IO ()', koje
koristimo samo zbog njihovih popratnih efekata, i koje nemaju što proslijediti
dalje. Kod monade 'Maybe' taj operator baš i nije tako koristan.

(Operator 'fail' služi za dojavu pogreške kod podudaranja uzorka. Više o tome
kasnije.)

Dakle, monada 'Maybe' je apstrakcija slijeda izračuna koji u nekom koraku može
ne uspjeti. Ako jedan od izračuna ne uspije, taj izračun vraća 'Nothing', i
cijeli izračun evaluira se u 'Nothing'. U suprotnom, ako svi izračuni uspiju,
dobivamo rezultat umotan u tipski konstruktor 'Just'.

Što daju sljedeći izrazi?

> v1 = Just 5 >>= return . (+5)
> v2 = Just 5 >> return 5
> v3 = Just 5 >> Just 6 >> return 7 >>= return . (+1)
> v4 = return 0 >>= Just . (+1) >> return 2
> v5 = find isUpper "Haskell"  >>= return . toLower
> v6 = Just 5 >>= return
> v7 = Just 5 >>= return >> return 6
> v8 = Just (2,3) >>= return . fst >>= return . (+1)
> v9 = Nothing >>= return . fst >>= return . (+1)
> v10 = Just 5 >>= const Nothing >>= return . (+1)
> v11 = Just 5 >> (Just 6 >> Just 7)
> v12 = (Just 5 >> Just 6) >> Just 7
> v13 = Just 3 >>= (\x -> Just (show x))
> v14 = Just 3 >>= (\x -> Just (show x)) >>= return . (++"!")

== MONADIČKI ZAKONI ==========================================================

Svaka instanca razreda 'Monad' trebala bi zadovoljavati MONADIČKE ZAKONE. Te
zakone kompajler ne provjerava (ne može ih se provjeriti zaključivanjem
temeljem tipova), pa programer mora sam osigurati da ti zakoni vrijede (u
suprotnom instanca neće biti prava monada i neće se ponašati očekivano). Zakoni
su:

  (1) return a >>= k  ==  k a
  (2) m >>= return  ==  m
  (3) m >>= (\x -> k x >>= h)  ==  (m >>= k) >>= h

Prvi zakon kazuje nam da 'return' jednostavno proslijeđuje svoju vrijednosti
idućoj akciji. Drugi zakon kazuje nam da ako odmah vratimo rezultat akcije 'm',
to je isto kao da smo pustili akciju 'm' da sama vrati svoj rezultat. (Drugim
riječima, nema smisla uzeti rezultat akcije i odmah ga vratiti.) Treći zakon je
asocijativnost operatora povezivanja '>>='. Znači da je svejedno kako grupiramo
akcije.

Kao poseban slučaj trećeg zakona, za operator '>>' vrijedi:

  m1 >> (m2 >> m3) = (m1 >> m2) >> m3

Ovo zapravo znači da možemo pisati

  m1 >> m2 >> m3

Treći zakon je zbunjujuć jer se čini da implicira kako poredak izvođenja nije
bitna. To nije istina: u monadi poredak izvođenja akcije jest bitan! Ali je
nebitno kako grupiramo akcije (sve dok zadržimo isti redoslijed, dobro je).
Zapamtiti: asocijativnost ne mijenja poredak izvođenja (ali komutativnost
mijenja!). Više na:
http://lambda-the-ultimate.org/node/2448

Zašto ovo ne radi:

  v15 = return 0 >>= return . (+1)

Zato što su funkcija 'return' i operator (>>=) polimorfni: ne znamo o kojem
točno tipu se radi (jedino što znamo jest da je instanca razreda 'Monad').
Moramo dodatno specificirati tip. Npr.:

> v16 = return 0 >>= return . (+1) :: Maybe Int
> v17 = return 0 >>= return . (+1) :: IO Int

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

Sljedeće funkcije definirajte unutar monade 'Maybe'.

1.1
- Napišite funkciju
  grandfathersPartnerForename :: Person -> Maybe String

1.2
- Pomoću 'Data.List.stripPrefix' napišite funkciju
  stripSuffix :: Eq a => [a] -> [a] -> Maybe [a]
  stripSuffix "ar" "bumbar" => Just "bumb"
  stripSuffix "ak" "bumbar" => Nothing
- Napišite funkciju 
  removeAffixes :: String -> String -> String -> Maybe String
  koja iz zadanog stringa uklanja prefiks i sufiks.
  removeAffixes :: "bu" "ar" "bumbar" => Just "mb"

== IO-MONADA =================================================================

Podatkovni konstruktor IO je također instanca monade. 

Prisjetimo se funkcija:

  putStrLn :: String -> IO ()
  getLine :: IO String

Možemo pisati:

> hello1 :: IO ()
> hello1 = putStrLn "Hello" >>= \_ -> putStrLn "Hello!"

odnosno jednostavnije

> hello2 :: IO ()
> hello2 = putStrLn "Hello" >> putStrLn "Hello!"

Zapravo, DO-blok je sintaktički šećer i mogli bismo pisati monadički kod bez
njega, samo porabom funkcija (>>=) i 'return'.

Npr. umjesto:

> main1 :: IO ()
> main1 = do
>   putStrLn "Upiši svoj sretan broj"
>   number <- getLine
>   putStrLn $ "Tvoj sretan broj je " ++ number

možemo pisati:

> main2 :: IO ()
> main2 = 
>   putStrLn "Upiši svoj sretan broj" >>
>   getLine >>= 
>   (\number -> putStrLn $ "Tvoj sretan broj je " ++ number)

Umjesto:

> askName1 :: IO String
> askName1 = do
>   putStrLn "Upiši ime"
>   s1 <- getLine
>   putStrLn "Upiši prezime"
>   s2 <- getLine
>   return $ s1 ++ " " ++ s2

možemo pisati:

> askName2 :: IO String
> askName2 = 
>   putStrLn "Upiši ime" >>
>   getLine >>= (\s1 -> 
>     putStrLn "Upiši prezime" >>
>     getLine >>= (\s2 -> 
>       return $ s1 ++ " " ++ s2))

Situacija je mrvicu složenija ako imamo podudaranje uzorka koje može ne uspjeti
(uzorak koji nije sačinjen od samo jedne varijable), npr.

> main3 = do
>   (x:_) <- getLine
>   putStrLn $ "Prvo slovo je " ++ [x]

Ovomu ekvivalentno je:

> main4 =
>   let ok (x:_) = putStrLn $ "Prvo slovo je " ++ [x]
>       ok _     = fail "pattern match failure"
>   in getLine >>= ok

Dakle općenita pravila za "rašećerivanje" DO-notacije su:

  do e                        =>   e
  do e1; e2; ...; en          =>   e1 >> do e2; ...; en
  do x <- e1; e2; ...; en     =>   e1 >>= \x -> do e2; ...; en
  do pat <- e1; e2; ...; en   =>   let ok pat = do e2; ...; en
                                       ok _   = fail "..."
                                   in e1 >>= ok

DO-notacija nije naravno primjenjiva samo na IO-monadu. Možemo ju koristiti za
bilo koju monadu. Npr., za 'Maybe':

Umjesto:

  grandmothersPartner3 :: Person -> Maybe Person
  grandmothersPartner3 p = mother p >>= mother >>= partner

možemo zašećeriti s:

> grandmothersPartner4 :: Person -> Maybe Person
> grandmothersPartner4 p = do
>   m <- mother p
>   g <- mother m
>   partner g

Refrazirajmo monadičke zakone u DO-notaciji.
  
  (1) return a >>= k    ==  k a

      do y <- return x  ==  k x
         k y

  (2) m >>= return  ==  m

      do x <- m     ==  m
         return x
  
  (3) m >>= (\x -> k x >>= h)  ==  (m >>= k) >>= h

      do x <- m                ==  do y <- do x <- m
         y <- k x                             k x
         h y                          h y

== VJEŽBA 2 ==================================================================

2.1. 
- Rašećerite ovu funkciju:
  main5 :: IO ()
  main5 = do
    xs <- getArgs
    h <- case xs of
      (f:_) -> do e <- doesFileExist f
                  if e then openFile f ReadMode else return stdin
      []    -> return stdin
    s <- hGetContents h
    putStr . unlines . sort $ lines s

2.2.
- Zašećerite DO-notacijom funkciju 'grandfathersPartnerForename' iz 
  zadatka 1.1.