Haskell - State, IO, record syntaxe, zipper
V dnešních cvičeních se nám hodí několik importů:
import Data.Char
import Control.Exception
import Network.HTTP
Říkali jsme si, že funkce v Haskellu jsou čisté, tj. jejich hodnoty závisí jen na jejich vstupních parametrech. To je sice pěkné a dobře se s tím pracuje, ale občas to je nepraktické. Představme si třeba, že chceme v programu pracovat se zásobníkem čísel. Můžeme si ho nadefinovat jako
type Zasobnik = [Int]
Pro práci se zásobníkem potom používáme typicky funkce jako push a pop. push přidává hodnotu na zásobník a pop vrací hodnotu z vrcholu zásobníku (a odebere ji). Pro náš zásobník je jednoduché je napsat.
push::Int -> Zasobnik -> Zasobnik
push h zas = h:zas
pop::Zasobnik -> (Int, Zasobnik)
pop (z:zas) = (z, zas)
Jak bychom teď napsali funkci, která odebere dvě hodnoty z vrcholu zásobníku, sečte je, a vrátí nový zásobník?
zasobnikTest::Zasobnik->(Int, Zasobnik)
zasobnikTest z = (a+b, nz)
where
(a, z1) = pop z
(b, z2) = pop z1
nz = push (a+b) z2
Není to těžké, ale je to celkem ukecané a nepřehledné, musíme se sami starat o předávání zásobníku mezi funkcemi. Přitom by bylo tak pěkné, kdybychom mohli používat třeba do notaci a zásobníku si vůbec nevšímat. Taková věc je v Haskellu možná a implementuje ji State monáda. Ta má dva typové parametry, typ stavu (s) a typ návratové hodnoty funkce (a). Zajímavé je, že uvnitř monády tentokrát nemáme samotné hodnoty těchto dvou typů, ale funkci, která vezme stav a spočítá návratovou hodnotu a nový stav. Musí to tak být, jinak bychom se museli o stav starat pořád sami a předávat si ho. Celá myšlenka této monády je v tom, že budeme postupně skládat funkce. Na začátku zadáme jako parametr počáteční stav a dál se o něj funkce budou starat samy a budou si ho i samy předávat (pomoci >>=).
data Stav s a = Stav {runState :: s -> (a, s)}
V definici Stav si můžete všimnout použití tzv. record syntaxe, ta vlastně pojmenovává funkci uloženou uvnitř Stav a zároveň vytváří funkci runState::Stav s a -> s -> (a, s), která nám vrátí funkci obsaženou ve Stav. Funkce pop a push potom můžeme přepsat tak, aby pracovaly se stavem, který obsahuje náš zásobník. Potřebujeme tedy, aby vracely něco typu Stav Zásobník b, kde b je libovolný návratový typ funkce. U popStento typ je Int (první hodnota ze zásobníku), u pushS použijeme jako typ (), kterému se také říká unit. Je to typ, který může obsahovat jen jednu hodnotu a to (). Odpovídá trochu typu void v jiných programovacích jazycích (NoneType v Pythonu). (Pozor v Haskellu je i typ Void, který dělá něco úplně jiného – je pro funkce, které nikdy nic nevrátí.)
popS::Stav Zasobnik Int
popS = Stav $ \(s:ss) -> (s,ss)
popS tedy zabalí do Stav funkci, která vezme stav, z něj odebere první prvek ten nastaví jako výslednou hodnotu a vrátí zásobník bez prvního prvku.
pushS::Int -> Stav Zasobnik ()
pushS x = Stav $ \ss -> ((),x:ss)
Na pushS vidíme, že funkce pro práci se stavem mohou mít i parametry. V tomto případě pushS dostane Int, ten přidá na začátek zásobníku a vrátí (). Není totiž asi žádná rozumná hodnota, kterou by pushS jinak mohla vrátit, tato návratová hodnota nás navíc nebude zajímat. Pojďme ze Stav udělat monádu: samotná monáda musí mít jen jeden typový parametr, implementovat jako monádu tedy budeme (Stav s) a ne jen samotný Stav.
První věc, kterou potřebujeme je napsat instanci pro Functor (Stav s), tzn. potřebujeme napsat funkci fmap::(a -> b) -> Stav s a -> Stav s b, měla by to tedy být funkce, která vezme funkci a->b, která stav úplně ignoruje, a aplikuje ji ve Stav s. Jediná rozumná implementace takové funkce bude vzít návratovou hodnotu ze Stav s a, na ní aplikovat funkci a vytvořit tak Stav s b. Samotný vnitřní stav by se neměl změnit.
instance Functor (Stav s) where
-- fmap::(a -> b) -> Stav s a -> Stav s b
fmap f x = Stav $ \s -> let (v, ns) = runState x s
in (f v, ns)
Na implementaci je možná vhodné podívat se podrobněji. runState x vytáhne funkci ze stavu x (druhého parametru fmap) a aplikuje ji na stav s(parametr nové funkce, kterou definujeme), tím získá výsledek a stav, na výsledek potom aplikuje f (první parametr fmap) a stav jen zkopíruje.
Jako další krok potřebujeme napsat instanci Applicative pro Stav s, tedy funkci pure::a -> Stav s a, která co nejjednodušeji zabalí hodnotu do Stav s, a operátor (<*>)::Stav s (a->b) -> Stav s a -> Stav s b.
Funkce pure je jednoduchá, když dostane hodnotu, tak vytvoří funkci, která jen zkopíruje stav a jako návratovou hodnotu nastaví hodnotu ze vstupu.
Operátor (<*>) je o něco komplikovanější. Napřed spustí runState na stav, který obsahuje funkci (a->b), potom spustí runState i na druhý parametr, tím dostane výsledek typu a a další nový stav. Na výsledek aplikuje funkci, která byla výsledkem prvního stavu a vrátí nejnovější stav.
instance Applicative (Stav s) where
-- pure:: a -> Stav s a
pure x = Stav $ \s -> (x, s)
-- (<*>)::Stav s (a->b) -> Stav s a -> Stav s b
sab <*> sa = Stav $ \s -> let (ab, ns) = runState sab s
(a, ns2) = runState sa ns
in (ab a, ns2)
Konečně můžeme napsat instanci Monad (Stav s), stačí už nám jen dodefinovat operátor (>>=)::Stav s a -> (a -> Stav s b) -> Stav s b, který vlastně řetězí dvě funkce se stavem za sebou. Napřed tedy spustí runState na svou levou stranu, a na výsledný stav aplikuje funkci, kterou má na pravé straně. Tím dostane nový stav a zavolá na něj runState.
instance Monad (Stav s) where
--(>>=)::Stav s a -> (a -> Stav s b) -> Stav s b
h >>= f = Stav $ \s -> let (a, newState) = runState h s
g = f a
in runState g newState
Nyní můžeme naší testovací funkci přepsat jednoduše pomoci do notace, je vidět, že kód je mnohem přehlednější a snadnější na pochopení, navíc se nemusíme o stav starat sami.
zasobnikTestS::Stav Zasobnik Int
zasobnikTestS = do
a <- popS
b <- popS
pushS (a+b)
return (a+b)
Pomoci State monády můžeme třeba implementovat i práci s náhodnými čísly. Napíšeme si jednoduchý lineární kongruenční generátor náhodných čísel.
type Rand t = Stav Int t
rand::Int -> Rand Int
rand max = Stav $ \s -> let x = (s*1664525+1013904223) `mod` 2^32
in (x `mod` max, x)
nahoda::Int -> Int -> Rand [Int]
nahoda 1 max = fmap pure $ rand max
nahoda n max = (:) <$> rand max <*> nahoda (n-1) max
seed::Int -> Rand ()
seed n = Stav $ \_ -> ((), n)
Jedna z nejdůležitějších monád v Haskellu je IO. V této monádě žije všechno, co chce nějakým způsobem komunikovat s vnějším světem. Můžete si to představovat třeba tak, že ta monáda se stará o to, aby si jednotlivé funkce mezi sebou předávaly nějaký stav. A ten stav je v tomto případě celý vnější svět (vnější z pohledu programu). Díky tomu potom funkce mohou měnit tento stav (výstup), případně z toho stavu něco zjišťovat (vstup). Tím jsme dosáhli toho, že se nám podařilo propojit svět funkci bez vedlejších efektů s požadavkem na to, mít vstupy a výstupy.
V Haskellu je běžné, že se vstupy a výstupy oddělují od vlastního provádění programu. Monáda IO by vám tedy neměla nikdy prolézt celým programem až k typům pomocných funkci někde hluboko v kódu. Naopak, IO by ve svém typu měly mít jen funkce, které vstup a výstup nutné potřebují dělat. Podle toho, že nějaká funkce má ve svém typu IO poznáte, že může mít nějaké vedlejší efekty.
Podívejte se třeba na funkci getLine, její typ je IO String. To znamená, že tahle funkce udělá nějaké vstupy a výstupy a vrátí nakonec String. Díky tomu, že tento String má před sebou ještě IO vidíme, že může být jiný při každém volání této funkce - funkce tedy má vedlejší efekty.
Už jsme viděli i funkci putStrLn, ta má typ String -> IO (), to znamená, že vezme String, udělá nějaký vstup a výstup a nic nevrací (tj. jen mění okolní svět).
My samozřejmě víme přesně, co tyhle funkce dělají – getLine načte jednu řádku že vstupu, putStrLn vypíše String na standardní výstup.
Napište teď program, který se zeptá uživatele na nějaký text a potom ho postupně po řádkách načítá a vypisuje na konzoli velkými písmeny. (Ve skutečnosti ho načte celý najednou, ale buffer je nastavený defaultně po řádkách, takže to vždy po konci řádky zpracuje.) Pokud byste chtěli načíst jen jednu řádku, můžete použít getLine. Jeden znak se načte pomocí getChar. Program ukončete pomocí Ctrl+C.
zakric :: IO ()
zakric = do
putStrLn "Zadej text: "
text <- getContents
let output = naVelka text
putStrLn output
naVelka :: [Char] -> [Char]
naVelka = map (toUpper)
Všimněte si několika věci: zakric má typ IO (), tj. je to funkce, která má nějaké vedlejší efekty a nakonec nic nevrací; naVelka je čistá funkce, která ve svém typu žádné IO nemá, taky by mít neměla, nedělá žádné vstupy a výstupy a nakonec je jí úplně jedno, kde ten String, se kterým pracuje, vezme; v do blocích se za let nepíše in. Pokud chceme v do bloku pojmenovat výstup z čisté funkce použijeme let, pokud z nějaké IO akce použijeme <-.
Načtení vstupu, jeho zpracování a výstup jsou tak běžné činnosti, že pro ně dokonce existuje hotová funkce, jmenuje se interact a pomoci ní můžeme přepsat předchozí příklad takhle:
iZakric :: IO ()
iZakric = do
putStrLn "Zadej text: "
interact naVelka
Tím, že se nám podařilo oddělit vstup a výstup od jejich zpracování se nám zároveň podařilo to, že samotné funkce, které vstupy a výstupy zpracovávají, vůbec nemusí vědět (ani nevi), odkud se data vzala. Mohla se klidně vzít i z nějakého souboru.
Můžeme si třeba podobným způsobem napsat program, který načte ze souboru čísla a na výstup vypíše jejich součet.
secti :: String -> IO ()
secti vstup = do
vstup <- readFile vstup
let vystup = zpracujSoucet vstup
putStrLn vystup
zpracujSoucet :: String -> String
zpracujSoucet v = show $ sum $ map (\x -> (read x)::Integer) $ lines v
Načtení celého souboru najednou, jak je uděláno v příkladu výše, se bát nemusíte. Pokud ho zpracováváte rozumně, Haskell ho celý najednou v paměti nikdy mít nebude. Jakmile zjistí, že některá data už nepotřebuje, zahodí je. Zpracování v příkladu úplně rozumné není, sum totiž používá foldl a ten potřebuje mít napřed celý seznam čísel. Pokud bychom místo foldl v sum použili foldl', potom by Haskell celý soubor zpracoval v konstantní paměti.
Pokud soubor neexistuje, Haskell vyhodí výjimku a pokud ji nikdo neodchytí, tak spadne. Haskell na výjimky reagovat umí, není s tím problém. My se tím moc zabývat nebudeme, jen si povíme o jedné funkci: handle
sectiExceptions vstup = handle ((\_ -> putStrLn "Soubor se nepodarilo otevrit")::IOException -> IO ()) $ do
vstup <- readFile vstup
let vystup = zpracujSoucet vstup
putStrLn vystup
Podobným způsobem můžeme číst i data ze sítě (potřebujeme modul Network.HTTP). Příklad funguje jen pro ASCII soubory, zkoušejte třeba s http://www.google.com/robots.txt.
stahni url fileName = do
response <- simpleHTTP $ getRequest url
print response
let body = fmap rspBody response
case body of
Left _ -> putStrLn "error"
Right content -> writeFile fileName content
V předchozím příkladu jste zároveň viděli typické použití typu Either a b = Left a | Right b. V případě chyby se její popis uloží do Left, pokud se chyba nestane, je výsledek v Right. Jedná se vlastně o rozšíření typu Maybe (a funguje podobně, navíc je to taky monáda).
ghc umí Haskell i kompilovat, k tomu je důležité, abychom měli metodu main::IO (). Typ IO () říká, že ta metoda pracuje se vstupy a výstupy (obecně s IO monádou) a nic nevrací. V modulu System.Environment je metoda getArgs :: IO [String], která vrací seznam parametrů z příkazové řádky (bez názvu programu, ten můžete dostat pomocí getProgName :: IO String).
Typický main obsahuje načtení vstupu (případně i parametrů) a jejich předání čistým funkcím, které už IO nepoužívají. Nakonec se zase výsledky těchto čistých funkci vypíšou (typicky zase přímo v main je volání vypisovacích funkcí).
V Haskellu vstup a výstup funguje striktně (tj. ne líně), ale streamovaně. To znamená, že data programem v Haskellu protečou, a pokud nejsou všechna najednou třeba, v paměti se neuloží. Striktnost vstupu a výstupu je důležitá jinak by výsledek programu mohl záležet na pořadí vyhodnocení (např. dvakrát getLine za sebou by vracel jiné výsledky, kdyby se druhý vyhodnotil dříve než první).
Defaultní chování ghc při kompilování je nepoužívání optimalizací. Pokud chcete optimalizace zapnout, stačí mu dát parametr -O, případně -O1 (znamená to samé). -O2 může použít i “nebezpečné” optimalizace, které mohou při troše smůly vést naopak ke zpomalení kódu. Dokumentace ke ghc tvrdí, že -O2 málokdy vytvoří rychlejší kód než -O.
Jak velké je zrychlení? Pokud např. použijeme kód, který jsme ukazovali výše (součet hodnot ze souboru) na sečtení miliónu čísel, zjistíme, že bez optimalizací to trvá cca 5.5 sekundy, s nimi jen 4.5 sekundy. Navíc s optimalizacemi vystačíme s menším zásobníkem (default je 8MB), bez nich ho potřebujeme zvýšit.
Ještě větší rozdíl uvidíme, když ho spustíme na prvních 100M čísel. Verze, která používá -O doběhne za 433 sekund a po celou dobu zabírá cca 3MB paměti. Oproti tomu verze bez optimalizaci sežere 1GB paměti a pak spadne (můžeme ji dát paměti více, ale stejně to nepomůže). Rozdíl je v tom, že GHC optimalizuje striktnost výpočtu a je schopné detekovat, že sum (což je vlastně foldl (+) 0) se dá vyhodnotit v konstantním prostoru (v zásadě z foldl udělá foldl' a navíc se postará o to, aby se soubor nenačítal celý, ale jen kousky, které jsou zrovna potřeba).
Předešlá diskuze není rozhodně sofistikovaný benchmark, má spíš ukázat, že se vyplatí Haskellovské programy kompilovat a pokud máte nějaký problém, je vhodné zapnout optimalizace.
Zkusme si ještě nakonec naimplementovat simulátor nedeterministického Turingova stroje. Ukážeme si na tom několik málo technik, které jsme ještě neviděli a procvičíme si práci s nedeterminismem.
První co budeme potřebovat je nějaký způsob, jak reprezentovat pohyb hlavy na páskách.
data Smer = L | R | N
Dále budeme potřebovat nějakou přechodovou funkci.
data Fce a b = Fce [((a,b),(a,b,Smer))]
A potom samotný Turingův stroj. Tady si všimněte definice pásky: jsou tam dva seznamy a jedna hodnota. Hodnota určuje symbol pod hlavou TS. Levý seznam je páska vlevo od hlavy (uložena pozpátku, takže na začátku seznamu je symbol, který je hned vlevo od hlavy) a v pravém seznamu je páska napravo od hlavy.
data TS a b = TS {
paska :: ([a],a,[a]) -- obousmerne nekonecna paska TS
, stav :: b -- aktualni stav TS
, fce :: Fce a b -- prechodova fce
, koncoveStavy :: [b] -- seznam koncovych stavu
, pos :: Int -- aktualni pozice od zacatku (pro vypis)
, minPos :: Int -- nejlevejsi pozice (pro vypis)
, maxPos :: Int -- nejpravejsi pozice (pro vypis)
}
Použili jsme tzv. record syntaxi, která nám kromě definice dat zároveň definuje i funkce, které jednotlivé položky vrací. Takže např. zavolání paska ts, kde ts je nějaký TS nám vrátí jeho pásku.
Ještě se nám hodí funkce, která vrátí symbol pod hlavou TS. Všimněte si triku s where, který nám umožňuje udělat pattern matching v těle funkce.
hlava :: TS a b -> a
hlava ts = a where (_,a,_) = paska ts
Funkce, která “pěkně” vypíše TS. Tentokrát jsme místo triku s where použili podobný trik s let.
showTS:: (Show a, Show b) => TS a b -> String
showTS ts = let
(xs,h,ys) = paska ts
b = stav ts
right = (maxPos ts) - (pos ts)
left = (pos ts) - (minPos ts)
in
show (reverse $ take left xs) ++ show h ++ show (take right ys) ++ "-" ++ show b
Funkce, která vrací všechny možnosti přechodové funkce aplikovatelné v daném stavu s daným symbolem pod hlavou.
findAll :: (Eq a, Eq b) => (a,b) -> Fce a b -> [(a,b,Smer)]
findAll (a,b) (Fce f) = [(x,y,s) | ((a1,b1),(x,y,s)) <- f, a==a1, b==b1]
Teď je potřeba naimplementovat jeden krok TS. Funkce je sice dlouhá, ale není moc těžká. Většina práce a triků se děje až v case na konci.
step :: (Eq a,Eq b) => TS a b -> [TS a b]
step ts = do -- vyuzijeme nedeterminismu list monady
let f = fce ts -- prechodova fce
let ((x:xs), p, (y:ys)) = paska ts -- paska a symbol pod hlavou
let s = stav ts -- stav
let kroky = findAll (hlava ts, stav ts) f -- mozne prechody
let ps = pos ts -- aktualni pozice na pasce
let minP = minPos ts -- nejlevejsi navstsivena pozice
let maxP = maxPos ts -- nejpravejsi navstivena pozice
(np, ns, d) <- kroky -- jeden mozny krok
case d of -- posun a zmena stavu podle kroku
L -> return ts {paska = (xs,x,np:y:ys), stav = ns, pos = ps - 1, minPos = min minP (ps - 1)}
R -> return ts {paska = (np:x:xs,y,ys), stav = ns, pos = ps + 1, maxPos = max maxP (ps + 1)}
N -> return ts {paska = (x:xs,np,y:ys), stav = ns}
Všimněte si posledních třech řádek. Record syntaxe nám umožňuje vytvořit upravenou kopii TS, aniž bychom museli opisovat zbytek informací, které se nemění. To se hodí, nemusíme totiž přepisovat všechny funkce, když se rozhodneme přidat do TS nějakou další informaci.
Nakonec napíšeme samotnou simulaci. Ta už je snadná. Stroje, které jsou v nějakém koncovém stavu už se dál nesimulují. Na ostatní se aplikuje funkce step. Funkce opět využívá nedeterminismu list monády.
sim::(Eq a, Eq b) => TS a b -> Int -> [TS a b]
sim ts 0 = return ts
sim ts maxS = do
stroj <- step ts
if (stav stroj) `elem` (koncoveStavy stroj) then
return stroj
else
sim stroj (maxS - 1)
Způsob, jakým jsme reprezentovali pásku TS se nazývá zipper. Umožňuje nám přístup v konstantním čase na jedno konkrétní místo v datové struktuře (v tomhle případě v seznamu). Kromě seznamu se dá použít i na stromu (tam je třeba si pamatovat, na jaké straně byl daný kousek přilepen). Můžete si ho představit tak, že strom (seznam) vezmete za to místo, kam chcete mít rychlý přístup a zvednete ho do vzduchu, co spadne dolů na jednu stranu je jedna polovina zipperu, co spadne na druhou je jeho druhá polovina (u TS jsme si navíc pamatovali prvek, za který jsme ho drželi).