Kate Konczycki

Operace na monádách

Spousta operací, které můžeme dělat na čistých typech, lze dělat i na monádách. Obecně platí, že obdoby pro čisté funkce, které pracují s monadickými strukturami, budou mít odvozený název.

Pokud se nějaká funkce nad běžnými typy jmenovala func, její odvozená varianta, jenž pracuje nad monádami, se bude jmenovat funcM. Podobně, pro aplikativní struktury se pojmenuje funcA. Pokud máme funkci, která dělá něco s monádami func, a chceme odvodit její variantu zahazující výsledky, pojmenujeme ji func_.

Vzpomeňme si na funkci map. Ta převáděla seznam na jiný seznam podle funkce. Co kdybychom však chtěli tento seznam použít jako seznam hodnot, které se mají změnit podle akce monadicky? Ukažme si, jak tyto funkce budou vypadat a jaká bude jejich sémantika:

Pokud bychom se chtěli přiblížit více k imperativnímu programování, můžeme najít funkce forM a forM_, které mají oproti mapům prohozené parametry. A jak se tyto funkce budou chovat v praxi?

half x = if even x then Just (x `div` 2) else Nothing

> map half [1,2,3,4]
[Nothing, Just 1, Nothing, Just 2] -- Každý výsledek je spočítán zvlášť

> mapM half [2,4,6]
Just [1,2,3] -- Zde jsou všechny výsledky
-- do
--     x1 <- half 2
--     x2 <- half 4
--     x3 <- half 6
--     ...
--     return [x1, x2, x3, ...]

> forM [2,3,4] half
Nothing -- Někde nastala chyba

> mapM_ half [2,4,6]
Just () -- Vše se provedlo správně

Problém monadického mapu je však to, že zpočátku máme seznam čistých hodnot. Co kdybychom ale naopak měli seznam již připravených akcí, a ty jsme chtěli provést sekvenčně po sobě? K tomu právě slouží funkce sequence :: Monad m => [m a] -> m [a] a její varianta zahazující výsledky sequence_ :: Monad m => [m a] -> m ().

> sequence [Just 1, Just 2, Just 3]
Just [1,2,3]

> sequence [Just (), Just (), Nothing, Just ()]
Nothing

> sequence_ [Just (), Just ()]
Just ()

-- mapM  == (sequence  . map)
-- mapM_ == (sequence_ . map)

Cvičení: Naprogramujte funkci, která zkontroluje, že všechny prvky v seznamu jsou definované.

Další zajímavé zobecnění je skládání funkcí, které vezme funkce typu b -> c a a -> b a složí je. Jejich zobecnění pak bude funkce (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c. Ta prostě vezme dvě akce a složí je. Protože monády se častěji píšou zleva doprava, existuje i její obrácená sestra (>=>).

quarter_composed = half >=> half
quarter_bind x = x >>= half >>= half

-- Všimněte si podobnosti se skládáním, když to obrátíme...
-- \x ->  f     (g     x)
-- \x -> (f  .   g) x
-- \x ->  f =<< (g =<< x)
-- \x -> (f <=<  g) x

Spousta funkcí, která pracuje se seznamy, má zobecněnou variantu, která místo funkce (a -> b) bere akci (a -> m b) a vrací seznam obalený do této monády. Seznam předpřipravených funkcí lze najít v modulu Control.Monad.

divSafe x y = if y == 0 then Nothing else x Just $ `div` y

> zipWithM divSafe [6,9,12] [2,3,2]
Just [3,3,6]

> zipWithM divSafe [6,9,12] [2,3,0]
Nothing

Důležité monády a práce s nimi

Nyní, když víme, co to monády jsou, jaký je jejich účel a jak s nimi pracovat, podívejme se na ty nejdůležitější.

Nejprve si všimněme, že pokud je nějaký typ přímo monáda, nemusíme zvlášť říkat, jak budou vypadat jejich instance funktoru nebo aplikativní struktury, protože vyplývají z chování monády:

fmap f m = m >>= (\x -> return f x)

pure = return
m1 <*> m2 = do
    f <- m1
    x <- m2
    return (f x)

Selhání výpočtu: Maybe a Either

Pokud máme nějaký postupný výpočet, který může v každém místě selhat, můžeme k tomuto účelu využít již několikrat zmiňovanou monádu Maybe. Podobná monáda, Either, navíc umožňuje poslat alternativní hodnotu reprezentující chybu.

data Either a b = Left a | Right b

instance Monad (Either a) where
    return = Right
    (Left a) >>= _ = Left a
    (Right b) >>= f = f b

> Left 5 >>= (\x -> return (2*x))
Left 5

> Right 7 >>= (\x -> return (2*x))
Right 14

K čemu to můžeme použít v praxi? Představme si třeba, že máme funkce, které pro danou osobu možná vrátí rodiče. My bychom rádi napsali funkci, která vrátí oba dědečky pro danou osobu pouze, pokud oba existují. Můžeme postupovat přímo, ale docela se nadřeme:

father :: Person -> Maybe Person
mother :: Person -> Maybe Person

grandfathers :: Person -> Maybe (Person, Person)
grandfathers x = case father x of
    Nothing -> Nothing
    Just f  -> case mother x of
        Nothing -> Nothing
        Just m  -> case father f of
            Nothing -> Nothing
            Just gf -> case father m of
                Nothing -> Nothing
                Just gm -> Just (gf, gm)

Monadicky si tím velmi zjednodušíme celou funkci, pokud se rozhodneme použít do syntaxi:

grandfathers x = do
    f <- father x
    m <- mother x
    gf <- father f
    gm <- father m
    return (gf, gm)

Nedeterministické výpočty pomocí seznamů

Seznamy jsou rovněž monády. Vzpomeňme si, jak se seznamy chovají aplikativně. V tom případě se vezme každá funkce s každým prvkem a všechny výsledky se uloží do jednoho seznamu.

Prohlédněme si signaturu funkce (>>=) specializovanou na seznamy. Tam chceme vzít seznam, pak funkci beroucí prvek seznamu vracející seznam a výsledek je zase seznam. Co to znamená? Každý prvek nahradíme seznamem a tyto seznamy pak spojíme dohromady do jednoho seznamu. Tuto operaci zachytíme funkcí concatMap a dostaneme:

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f l = concat (map f l)

instance Monad [] where
    return x = [x]
    -- (>>=) :: [a] -> (a -> [b]) -> [b]
    l >>= f = concatMap f l

> [1,2,3] >>= (\x -> [x, 10*x])
[1,10,2,20,3,30]

> [1,2,3] >> ['a','b']
['a','b','a','b','a','b']
-- každý prvek nahradíme dvěma znaky a, b

Co tedy znamenají seznamy jakožto analogie naších sekvenčních výpočtů? Inu, nedeterminismus. Seznam v určité chvíli popisuje množinu všech výsledků nedeterministického výpočtu. Reakce pak zvolí každý z výsledků a z něj může nedeterministicky vypočítat libovolně mnoho dalších výsledků.

Jako příklad si třeba ukažme, jak spočítat všechny podmnožiny konečného seznamu nebo všechny permutace. Všimněme si, že každý řádek obsahující <- odpovídá nedeterministiké volbě.

subsets [] = [[]]
subsets (l:ls) = do
    rest <- subsets ls
    [rest, (l:rest)]
    -- vracíme více výsledků

permutations [] = [[]]
permutations l = do
    -- permutations(l, (elm:perm)) :-
    index <- take (length l) [0..]
    let elm = l !! index
    let subl = (take index l) ++ (drop (index + 1) l)
    -- select(l, elm, subl),
    perm <- permutations subl
    -- permutations(subl, perm).
    return (elm:perm)

> subsets [1,2]
[[],[1],[2],[1,2]]

> permutations [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Cvičení: Naprogramujte funkci combinations :: Integer -> [a] -> [[a]], která pro k vrátí všechny k-tice prvků v původním pořadí.

Cvičení: Naprogramujte funkci combinationsRepeat :: Integer -> [a] -> [[a]], která vrací všechny kombinace a prvky se navíc mohou opakovat.

Už víme, že seznamy mohou do jisté míry nahradit množinový zápis použitím aplikativních postupů. Co jsme však neuměli vyjádřit, byla podmínka. I to teď pomocí monád zvládneme. Všimněte si mimochodem i podobnosti s množinovým zápisem!

guard :: Bool -> [()]
guard x = if x then [()] else []

pythagoreanTriples n = [(x, y, z) |
    x <- [1..n], y <- [x..n], z <- [y..n], (x*x + y*y == z*z)]

pythagoreanTriplesM n = do
    x <- [1..n]
    y <- [x..n]
    z <- [y..n]
    guard (x*x + y*y == z*z)
    return (x, y, z)

> [1,2,3] >>= \x -> guard (odd x)
[(),()]
-- guard "vyfiltruje" ty prvky, pro které neplatí podmínka

> [1,2,3] >>= \x -> guard (odd x) >> return x
[1,3]

> guard True >> [7]
[7]

> guard False >> [3]
[]

> pythagoreanTriplesM 13
[(3,4,5),(5,12,13),(6,8,10)]

Cvičení: Naprogramujte funkci subsum :: Num a => a -> [a] -> [a], která vrátí všechny podmnožiny seznamu, jejichž součet je daný parametr.

Vstup a výstup

Nejdůležitější úloha monád a vlastně i důvod, proč původně vznikly, je monáda IO. Ta slouží pro to, aby mohl mít čistě funkcionální Haskellový program přístup k vnějšímu světu a mohl interagovat s uživatelem. vstup a výstup jsou totiž vedlejší efekty.

nezapomeňme, že akce je funkce a nelze z ní jen tak vytáhnout její hodnotu. Ta hodnota závisí na tom, jak se akce provede a ne vždy může nějakou hodnotu mít (prázdný seznam, Nothing). Jediné, co jistě můžeme, je na základě hodnoty vytvořit další akci, ať třeba nic neudělá, kterou pak můžeme zavolat na čistou hodnotu nebo svázat s jinou akcí. Zatímco u Maybe a seznamů jsme sice mohli podvádět rozbalením vnitřní struktury, u IO si už to dovolit nemůžeme.

Podívejme se teď na základní IO funkce, které nám poskytuje standardní knihovna Haskellu.

Další IO akce lze najít v modulu System.IO.

Jako vstupní bod programu definuje Haskell funkci main :: IO (). Pokud program zkompilujeme a spustíme přímo, bez použití interaktivního módu, tato funkce provede IO akci jí definovanou.

Ukažme si příklad jednoduchého programu, který načte počet opakování a řádek, následně tento řádek tolikrát zopakuje s tím, že v prvním zopakování budou všechna písmena velká.

module Main where

import Data.Char (toUpper) -- chceme zvětšovat znaky
import Control.Monad -- monadické operátory

-- Načti číslo
readInteger :: String -> Integer
readInteger = read

-- Změň první prvek
mapFirst _ [] = []
mapFirst f (x:xs) = (f x) : xs

main = do
    putStrLn "Please, give us number."
    n <- readInteger <$> getLine -- načti n jako číslo
    putStrLn "Please, give us a line to replicate."
    line <- getLine -- načti řádek
    let lines = (mapFirst . map) toUpper $ replicate n line -- připrav řádky
    mapM_ putStrLn lines -- vypiš je

Spuštění a použití programu pak může vypadat třeba takto:

$ ./program
Please, give us number.
3
Please, give us a line to replicate.
Hello, outside world from Haskell!
HELLO, OUTSIDE WORLD FROM HASKELL!
Hello, outside world from Haskell!
Hello, outside world from Haskell!
$ exit

Cvičení: Napište program, který na vstupu dostane na jednom řádku seznam čísel oddělených mezerou a vypíše součet jejich druhých mocnin.

Cvičení: Napište program, který spočítá počet mezer na vstupu. Může se hodit modul Data.Char, z něj funkce isSpace.

Držení vnitřního stavu

Problém se spoustou funkcí jako map nebo fold je, že přijímají pouze čisté funkce. To znamená, že mezi jednotlivými prvky seznamu si nemůžeme jen tak snadno posílat informaci, či vnitřní stav.

Samozřejmě, celé to můžeme obejít tak, že si budeme stav posílat explicitně jako parametr funkce a pak budeme vracet pozměněný stav společně s návratovou hodnotou.

Jako příklad práce se stavem si představíme pseudonáhodný generátor. Ten funguje jednoduše. Na začátku mu dáme počáteční hodnotu seed. Posléze při dotazu na náhodné číslo něco s touto hodnotou uděláme, čímž dostaneme hledané pseudonáhodné číslo a nový seed. Dotaz na další číslo však potřebuje tento nový seed.

type RandSeed = Int

randInt :: Int -> RandSeed -> (Int, RandSeed)
randInt max seed = (n, newseed)
    where
        newseed = (1664525 * seed + 1013904223) `mod` (2^32)
        n = (newseed `mod` max)

> randInt 100 1
(48,1015568748)
> randInt 100 1015568748
(67,1586005467)
> randInt 100 1586005467
(38,2165703038)
> randInt 100 2165703038
(65,3027450565)

Vida, umíme tedy generovat náhodná čísla, ale je to nepříjemné v tom, že si musíme pokaždé seed posílat do dalšího zavolání. Když si třeba chceme napsat funkci, která nám vrátí tři náhodná čísla, musíme postupovat přibližně takto:

rand3Num max seed0 = ([n1,n2,n3],seed3)
    where
        (n1,seed1) = randInt max seed0
        (n2,seed2) = randInt max seed1
        (n3,seed3) = randInt max seed2

> rand3Int 100 1
([48,67,38],2165703038)

Abychom si takto nemuseli posílat stav explicitně přes každé volání funkce pracující se stavem, pořídíme si stavovou monádu. Ta má v sobě schovaný aktuální stav a popisuje akce, jenž mohou tento stav měnit nebo k němu přistupovat, a vrací běžnou hodnotou funkce.

Typ stavu a typ návratu jsou nezávislé, a navíc obvykle se může typ návratu měnit. Typ stavu naopak obvykle zůstává pořád stejný. Tudíž, můžeme mít sice libovolnou dvojici typu stavu a výsledku, ale budeme požadovat, že se typ stavu nebude v průběhu výpočtu měnit.

newtype State s a = State { runState :: s -> (a, s) }

-- Funkce balící do stavu
-- Budeme používat místo konstruktoru
state :: (s -> (a, s)) -> State s a
state x = State x

Slovo newtype je v podstatě to samé, co data pouze umožňující právě jeden konstruktor s právě jedním parametrem. Takto můžeme nějaký jiný typ obalit rozlišitelnou dodatečnou informací pro typový systém, narozdíl od type.

Rozmyslíme si nyní, jak se má stavová akce chovat jako monáda. Rozepíšeme si typy jednotlivých operací a uvážíme, co se musí dít, abychom je splnili.

fmap  :: (a -> b) -> State s a -> State s b
pure  :: a -> State s a
(<*>) :: State s (a -> b) -> State s a -> State s b
(>>=) :: State s a -> (a -> State s b) -> State s b

-- Rozbalíme typ stavu
fmap  :: (a -> b) -> (s -> (a, s)) -> (s -> (b, s))
pure  :: a -> (s -> (a, s))
(<*>) :: (s -> ((a -> b), s)) -> (s -> (a, s)) -> (s -> (b, s))
(>>=) :: (s -> (a, s)) -> (a -> (s -> (b, s))) -> (s -> (b, s))

Funkce fmap je jednoduchá. Vezmeme transformaci, ze stavu spočítáme výsledek, ten transformujeme a vrátíme transformovaný výsledek plus nový stav. Podobně, funkce pure prostě vezme konstantu a vytvoří stavový výpočet, který prostě nezávisle na stavu vrátí tuto konstantu, aniž by stav jakkoliv změnila.

Operace <*> spočítá z dodaného stavu první funkci, pak pomocí nového stavu vypočítá hodnotu, čímž dostane ještě novější stav. Pak jen vrátí výsledek z vypočítáné funkce a hodnoty a přibalí k tomu nový stav.

Nakonec máme operaci >>=, která intuitivně zřetězí dva stavové výpočty za sebe. Tudíž nejprve ze stavu spočítá výsledek a nový stav. Pak na výsledek aplikuje reakci, která vytvoří novou stavovou akci. Nakonec do této nové stavové akce vloží spočítaný stav a vrátí zřetězený výsledek.

instance Functor (State s) where
    fmap f sx = state $ \s0 ->       -- Bereme stav 0
        let (x, s1) = runState sx s0 -- Spočítáme x a stav 1
        in  (f x, s1)                -- Spočítáme (f x) a stav 1

instance Applicative (State s) where
    pure x = state $ \s -> (x, s)    -- Bere stav, vracíme x a stav

    sf <*> sx = state $ \s0 ->       -- Bereme stav 0
        let (f, s1) = runState sf s0 -- Spočítáme f a stav 1
            (x, s2) = runState sx s1 -- Spočítáme x a stav 2
        in  (f x, s2)                -- Spočítáme (f x) a stav 2

instance Monad (State s) where
    sx >>= f = state $ \s0 ->        -- Bereme stav 0
        let (x, s1) = runState sx s0 -- Spočítáme x a stav 1
            g       = f x            -- Transformujeme x na akci g
        in runState g s1             -- Vrátíme výsledek akce g se stavem 1

Už máme prostředky k tomu, abychom pomocí stavové monády reprezentovali náš náhodný generátor. Vytvoříme si k tomu nový typ, pak přepsání funkce do stavové akce bude triviální. Nakonec můžeme využít monadický map k tomu, abychom přepsali naši funkci pro generaci tří čísel.

type RandGen a = State RandSeed a

randIntS :: Int -> RandGen Int
randIntS = (state . randInt)

rand3IntS = replicateM 3 randIntS

> runState (randIntS 100) 12345
(68,87628868)

> runState (rand3IntS 100) 1
([48,67,38],2165703038)

Akce manipulující se stavem

Nadefinujeme si jednoduché funkce, které nám zpříjemní práci se stavovými akcemi. Konkrétně budou nastavovat nebo zjišťovat aktuální stav, případně jej změní pomocí nějaké funkce. Tyto funkce víceméně budou odpovídat přiřazování a čtení proměnné v procedurálním programování.

return :: a -> State s a
-- Již máme z definice monády, vrátí hodnotu beze změny stavu

get :: State s s
get = state $  \s -> (s, s)
-- Získej hodnotu stavu

put :: s -> State s ()
put x = state $ \s -> ((), x)
-- Ulož novou hodnotu stavu

modify :: (s -> s) -> State s ()
modify f = do
    x <- get
    put $ f x
-- Změň hodnotu stavu podle funkce f

Taktéž si vytvoříme funkce, které nám rychle umožní získat pouze výslednou hodnotu nebo výsledný stav z provedené stavové akce.

evalState :: State s a -> s -> a
evalState action state = fst $ (runState action) state
-- Proveď stavovou akci a získej výsledek

execState :: State s a -> s -> s
execState action state = snd $ (runState action) state
-- Proveď stavovou akci a vrať stav

Ukažme si teď s pomocí pomocných funkcí a stavové monády průběh jednoduché hry. Hra bude mít dva stavy: dvojici čísel a číslo tahu hráče. Stav hry měníme znaky, kde * znamená konec tahu, + a - znamenají přičtení nebo odečtení čísla daného hráče. Jakýkoliv jiný znak je ignorován. Výsledek hry je rozdíl skóre prvního a druhého hráče.

type GameState = (Integer, Integer, Bool)
gameStart = (0, 0, True)

-- Pomocné funkce nad GameState
mapFstScore f (a, b, c) = (f a, b, c)
mapSndScore f (a, b, c) = (a, f b, c)
diffScore (a, b, c) = a - b

turn (_, _, c) = c
swapTurn (a, b, c) = (a, b, not c)

-- Specializované čtení stavu
getScore :: State GameState Integer
getScore = diffScore <$> get
getTurn :: State GameState Bool
getTurn = turn <$> get

-- Nelze zapsat přímo (-1) jako funkci...
dec :: Num a => a -> a
dec x = x - 1

gameRun :: Char -> State GameState Integer
gameRun cmd = do
    firstTurn <- getTurn -- Získáme stav
    let mapScore = if firstTurn then mapFstScore else mapSndScore
    -- Vybereme pozici hráče na tahu
    case cmd of
        '+' -> modify $ mapScore (+1) -- Hráč na tahu získává bod
        '-' -> modify $ mapScore dec  -- Hráč na tahu ztrácí bod
        '*' -> modify $ swapTurn      -- Hráč končí svůj tah
        _   -> return ()              -- Nic se neděje
    getScore -- Vracíme rozdíl bodů
    -- score <- getScore
    -- return score

> runState (gameRun '+') gameStart
(1,(1,0,True))

> runState (gameRun '-') gameStart
(-1,(-1,0,True))

> runState (gameRun '*') gameStart
(0,(0,0,False))

> evalState (forM "++-*-++--*" gameRun) gameStart
[1,2,1,1,2,1,0,1,2,2]

> evalState (forM "--++*++--+*" gameRun) (1,-1,True)
[1,0,1,2,2,1,0,1,2,1,1]

> evalState (forM_ "++-*-++--*" gameRun >> getScore) gameStart
2