Haskell - monády
V Haskellu jde používat i typy, které se v jiných jazycích vyjadřují těžko např. se v nich používají speciální hodnoty (jako třeba null). Užitečný typ je Maybe a, který může obsahovat buď hodnotu typu a (Just a), nebo nic (Nothing). Udělejme si jeho klon (použijeme češtinu, abychom nekolidovali s vestavěným).
data Mozna a = Proste a | Nic deriving (Show)
Tento typ nám umožní nadefinovat funkci i tam, kde normálně definována není, prostě v těch případech vrátíme Nothing (nebo Nic v naší definici).
Můžeme třeba napsat tzv. bezpečný logaritmus nebo bezpečnou odmocninu.
safeLog :: Double -> Mozna Double
safeLog x | x <= 0 = Nic
| otherwise = Proste (log x)
safeSqrt :: Double -> Mozna Double
safeSqrt x | x < 0 = Nic
| otherwise = Proste (sqrt x)
Co kdybychom chtěli spojit odmocninu a logaritmus? Spočítat bezpečně odmocninu logaritmu nějakého čísla?
safeSqrtLog :: Double -> Mozna Double
safeSqrtLog x = f (safeLog x)
where
f Nic = Nic
f (Proste x) = safeSqrt x
Typ Mozna se může hodit i v jiných případech, např. když chceme napsat funkci, která hledá nějaký prvek v seznamu, a pokud ho najde, tak vrátí jeho index. Pokud ho nenajde, může klidně vrátit Nic. Bez typu Mozna by musela vracet nějakou zvláštní hodnotu (třeba -1), nebo vyhodit výjimku.
najdi :: Eq a => [a] -> a -> Mozna Int
najdi xs x = najdi' xs x 0 -- pocitame od 0
najdi':: Eq a => [a] -> a -> Int -> Mozna Int
najdi' [] _ _ = Nic
najdi' (x:xs) y n | y == x = Proste n
| otherwise = najdi' xs y (n+1)
Podobným způsobem můžeme napsat i bezpečné verze funkcí, které normálně vyhazují výjimku, pokud se jim něco nelíbí (např. head a tail na prázdném seznamu).
safeHead :: [a] -> Mozna a
safeHead [] = Nic
safeHead xs = Proste (head xs)
safeTail :: [a] -> Mozna [a]
safeTail [] = Nic
safeTail (_:xs) = Proste xs
Napište teď funkci, která vyhledá v seznamu xs prvek, který je na prvním místě v seznamu ys. Použijte naše bezpečné funkce.
najdiPrvni:: Eq a => [a] -> [a] -> Mozna Int
najdiPrvni xs ys = f xs (safeHead ys)
where f xs (Proste y) = najdi xs y
f _ Nic = Nic
Spojování funkci, které vrací Maybe (nebo Mozna) je trochu škaredé, ale mohla by se dát napsat funkce, která ho udělá obecně?
Napište funkci lbind, která dostane funkci a -> Mozna b a hodnotu typu Mozna a a vrátí Mozna b, tj. spojí funkce dohromady podobně, jako (.) spojuje normální funkce.
lbind::(a->Mozna b)->Mozna a -> Mozna b
lbind f Nic = Nic
lbind f (Proste y) = f y
Náš bezpečný logaritmus odmocniny se pak dá napsat jako
lbSafeSqrtLog x = lbind safeSqrt (safeLog x)
A co naše vyhledání prvního prvku? To je maličko složitější, protože najdi je binární funkce, ale není to nic nezvládnutelného.
lbNajdiPrvni xs ys = lbind (najdi xs) (safeHead ys)
Pokud bychom chtěli, aby složení bylo podobnější obvyklému skládání, můžeme využít infixovou notaci
lbSafeSqrtLog' x = safeSqrt `lbind` safeLog x
Podobně samozřejmě můžeme napsat totéž pro naše hledání prvního prvku.
Pokud budeme používat vestavěné Maybe, můžeme použít i vestavěný lbind operátor (=<<).
mSafeLog :: Double -> Maybe Double
mSafeLog x | x <= 0 = Nothing
| otherwise = Just (log x)
mSafeSqrt :: Double -> Maybe Double
mSafeSqrt x | x < 0 = Nothing
| otherwise = Just (sqrt x)
mSafeSqrtLog x = mSafeSqrt =<< mSafeLog x
S pomoci tohoto bind musíme číst funkce zprava doleva, lépe se čte naopak, ale ani to není problém naprogramovat.
Pracujme zase s naším typem Mozna, pak si totéž ukážeme na standardním Maybe.
Napišme si tedy vlastní rbind, který bude parametry brát v opačném pořadí než lbind.
rbind :: Mozna a -> (a -> Mozna b) -> Mozna b
rbind x f = lbind f x
rbSafeSqrtLog :: Double -> Mozna Double
rbSafeSqrtLog x = safeLog x `rbind` safeSqrt
Operátor (>>=) je obdobou našeho rbind operátoru pro standardní typ Maybe.
rmSafeSqrtLog :: Double -> Maybe Double
rmSafeSqrtLog x = mSafeLog x >>= mSafeSqrt
Tento zápis můžete také číst tak, že se napřed aplikuje bezpečný logaritmus na x a potom teprve bezpečná odmocnina na výsledek. Trochu to začíná připomínat procedurální programování.
Haskell ve skutečnosti má speciální syntaxi, která procedurální programování připomíná ještě o něco víc.
dSafeSqrtLog :: Double -> Maybe Double
dSafeSqrtLog x = do
y <- mSafeLog x
mSafeSqrt y
Tento zápis má připomínat to, že do y se uloží mezivýsledek a ten se potom o řádek dál aplikuje, ale ve skutečnosti jde pořád jen o ten samý výpočet jako jsme viděli před chvílí. Celá do konstrukce je jen syntakticky cukr.
Občas se hodí do řetězu funkci, které vrací Mozna a, přidat i nějakou funkci která vrací jen a. Potom se nám hodí funkce, která převede a na Mozna a. Této funkci, se říká return, my ji budeme říkat vrat a její implementace je jednoduchá.
vrat :: a -> Mozna a
vrat x = Proste x
Když máme takovou funkci, můžeme snadno napsat třeba součet bezpečné odmocniny a bezpečného logaritmu.
dSafeLogPlusSqrt x = do
y <- mSafeLog x
z <- mSafeSqrt x
return (y + z)
Říkali jsme, že do notace je jen syntakticky cukr. Jak se ale dá horní výraz přepsat bez ní? (pro pokročilé Haskellisty, nemusíte umět)
mSafeLogPlusSqrt = (\x -> mSafeLog x >>= (\y -> mSafeSqrt x >>= (\z -> return (y+z))))
Všimněte si postupného skládání funkcí, k pojmenování y (odpovídající y <-) dojde až uvnitř druhé anonymní funkce. K pojmenování z ještě o kousek dál.
Náš typ Mozna se od Maybe pořád maličko liší. Např. tím, že pro něj nemůžeme používat do notaci, takže napsat pomoci něj předešlou funkci by bylo trochu nepřehledné
safeLogPlusSqrt = (\x -> safeLog x `rbind` (\y -> safeSqrt x `rbind` (\z -> vrat (y+z))))
Pokud chceme používat do notaci i pro náš typ Mozna, je potřeba říct, že Mozna patří do třídy Monad, ta je od verze GHC 7.10 (březen 2015) automaticky ve třídě Applicative (která sama je podtřída třídy Functor). Je tedy třeba ještě napsat instance pro Applicative Mozna a Functor Mozna.
instance Functor Mozna where
fmap f Nic = Nic
fmap f (Proste a) = Proste (f a)
Funkce fmap je zajímavá sama o sobě, umožňuje nám vzít funkci, která pracuje s běžnými typy a aplikovat ji třeba na typ Mozna. Například, když chceme k Just 1 (::Mozna Int) přičíst číslo 3 (::Int), napíšeme fmap (+3) (Just 1) a dostaneme výsledek Just 4.
instance Applicative Mozna where
pure = vrat
Nic <*> _ = Nic
(Proste f) <*> m = fmap f m
Funkce pure by měla zadanou hodnotu zabalit do Applicative co nejjednodušším způsobem. V našem případě odpovídá přesně naší funkci return. Operátor (<*>) má typ Mozna (a -> b) -> Mozna a -> Mozna b, “vybalí” tedy funkci z aplikativního funktoru, a potom udělá fmap na funktor, který dostane jako vstup. To se může hodit, například v případě, že chceme sečíst dvě čísla zabalená v nějakém aplikativním funktoru (třeba monádě Mozna). Můžeme pak psát pure (+) <*> Proste 3 <*> Proste 5 (a dostaneme Proste 8). Funkce pure nám dovolila zabalit funkci do aplikativního funktoru a potom ji použít na parametry, které v tomto funktoru jsou. Můžeme se na (<*>) dívat také jako na vylepšený fmap. Zapisovat pure (+) na začátek může být zdlouhavé, ale existuje i operátor <$>, který funkci napřed do funktorů zabalí a potom se chová jako <*>. Předchozí příklad bychom mohli tedy přepsat jako (+) <$> Proste 3 <*> Proste 5.
instance Monad Mozna where
(>>=) = rbind
return = pure -- od GHC 7.10 neni treba, je to defaultni implementace
A teď můžeme používat do notaci i pro naší třídu Mozna.
safeLogPlusSqrt' x = do
y <- safeLog x
z <- safeSqrt x
return (y + z)
Maybe není jediná monáda, která v Haskellu je, je to spíš jeden z jednodušších příkladu použití monád. Podívejme se na další.
Zkusme si zahrát piškvorky na hrací ploše 3x3. Hrací plochu můžeme reprezentovat jako seznam devíti pozic, přičemž na každé pozici je '.', 'x' nebo 'o'.
Napišme si funkci, která dostane symbol, za který hrajeme ('x', nebo 'o') a aktuální hrací plochu a vrátí nám všechny možné hrací plochy po jednom tahu.
dalsiTahy :: Char -> [Char] -> [[Char]]
dalsiTahy t xs = tahy ("", xs) t
Napíšeme si ještě pomocnou funkci tahy. Všimněte si použití rozdělení plochy na dvě části - jednu, kterou už jsme zpracovali, a druhou, se kterou právě pracujeme. Díky tomu celou plochu projdeme jen jednou.
tahy :: ([Char], [Char]) -> Char -> [[Char]]
tahy (_,[]) _ = []
tahy (x,y:ys) t | y == '.' = (x ++ (t:ys)) : tahy (x++[y], ys) t
| otherwise = tahy (x++[y], ys) t
Ještě se nám hodí převod plochy na čitelnější String.
plochaStr xs = "---\n" ++ take 3 xs ++ "\n" ++ take 3 (drop 3 xs) ++ "\n" ++ take 3 (drop 6 xs) ++ "\n"
Jak teď zjistíme, jak bude plocha vypadat po odehrání jednoho tahu hráče 'o', jestliže na začátku byl jeden křížek uprostřed? To se dá snadno zjistit pomoci naší funkce dalsiTahy.
poJednomTahu :: [[Char]]
poJednomTahu = dalsiTahy 'o' "....x...."
A jak to bude vypadat po dvou tazích? Napřed 'o' a pak 'x'.
poDvouTazich :: [[Char]]
poDvouTazich = concat (map (dalsiTahy 'x') (dalsiTahy 'o' "....x...."))
Jak byste to napsali dál po třech, po čtyřech a po pěti tazích? Funkce se nám prodlužuje a znepřehledňuje. Nicméně můžeme využít toho, že i seznam je monáda a chová se přesně tak, jak by se nám hodilo – bind dělá právě ten map a concat, který potřebujeme. Takže funkce poDvouTazich se pomoci monádového zápisu dá napsat jako:
mPoDvouTazich = ["....x...."] >>= dalsiTahy 'o' >>= dalsiTahy 'x'
Nebo pomocí do notace
dPoDvouTazich = do
x <- ["....x...."]
y <- dalsiTahy 'o' x
dalsiTahy 'x' y
Seznamy se chovají právě takhle, protože tím umožňují zachytit nedeterminismus výpočtu. Funkce prostě vrací všechny možnosti, které mohou nastat; postupně další a další větvení nabaluje do dalších a dalších seznamů.
Ted už dokonce umíme napsat i seznam všech uspořádaných dvojice bez toho, abychom potřebovali list comprehension.
usporadaneDvojice xs ys = do
x <- xs
y <- ys
return (x,y)
uD xs ys = xs >>= (\x -> (ys >>= \y -> return (x,y)))