Binární stromy a operace s nimi
Již umíme pracovat se seznamy a máme k dispozici způsob, jak si vytvořit vlastní rekurzivní struktury. Zaměříme se tedy nyní na stromy, konkrétněji binární.
Nejprve si vytvoříme strukturu pro stromy. Budeme očekávat, že listy mohou v sobě držet nějakou dodatečnou informaci, která se může lišit od vnitřních vrcholů.
Pokud bychom chtěli, aby listy neobsahovaly žádnou hodnotu, můžeme jako jejich
typ použít jednoprvkový typ ()
. Naopak, pokud bychom chtěli mít užitečná data
jen v listech, můžeme pro vnitřní vrcholy použít typ ()
.
My však budeme nyní pracovat zásadně se stromy, které data v listech nemají, tak si pro ně vytvoříme nový ADT. Zjednodušíme si tím Pattern Matching.
data GeneralTree a b = Leaf b | Node (Tree a b) a (Tree a b) deriving (Show, Eq) type TreeEmptyLeaf a = GeneralTree a () -- Listy nemají data type TreeOnlyLeaf a = GeneralTree () a -- Pouze listy mají data type ExpressionTree = GeneralTree Operation Integer -- Strom výrazu, Operation je nějaký typ pro operace data Tree a = Ext | Node (Tree a) a (Tree a) deriving (Show, Eq) -- Tuto definici budeme používat -- Protože listy nemají data, považujeme je za externí vrcholy
Cvičení: Napište funkci depth :: Tree a -> Integer
, která spočítá hloubku
stromu.
Nyní se na chvíli zaměříme na binární vyhledávací stromy, zatím bez vyvažování.
Protože již známe třídu Ord
, budeme porovnávat pomocí této třídy. Vkládání
do takového stromu je přímočará rekurzivní funkce.
insert :: Ord a => a -> Tree a -> Tree a insert x Ext = Node Ext x Ext insert x (Node l y r) = case compare x y of LT -> Node (insert x l) y r EQ -> Node l y r GT -> Node l y (insert x r)
Funkce compare
je další funkce definovaná třídou Ord
, která vrací výsledek
porovnání jako jednu z možností LT | EQ | GT
.
Cvičení: Naprogramujte funkci find :: Ord a => a -> Tree a -> Bool
, která
odpovídá, zda je prvek ve stromu.
Cvičení: Naprogramujte funkci delete :: Ord a => a -> Tree a -> Tree a
,
která smaže prvek ze stromu.
Když umíme přidávat vrcholy do libovolného stromu, můžeme rovnou napsat i funkci, která libovolný seznam převede na vyhledávací strom. Jediné, co musí seznam splňovat je, že jeho prvky musí být porovnatelné.
listToBST :: Ord a => [a] -> Tree a listToBST = foldr insert Ext
Cvičení: Mějme vyhledávací stromy jako multimnožinu, tedy že kromě náležení
prvku si též pamatují jeho četnost. Vložení prvku pak způsobí přičtení tohoto
množství, pokud se v něm již nachází. Vyberte typ tohoto stromu a pak pro něj
naprogramujte funkci find :: Ord a => MultiBST -> a -> Integer
vracející
četnost hledaného prvku. Dále upravte insert
a delete
, aby s četnostmi
pracoval.
Cvičení: Pro multimnožinový strom definujte funkci BMSTtoList
, která vrátí
uspořádaný seznam, který každý prvek obsahuje tolikrát, jaká byla jeho četnost.
Papír ze stromů, aneb zobecňujeme
Seznam jsme na vyhledávací strom převedli jeho jednoduchou redukcí. Mohli bychom podobně stromy redukovat na seznam?
Spousta operací se stromy funguje na bází prohledávání do hloubky, kdy něco provedeme s oběma syny a pak výsledek zkombinujeme s obsahem vrcholu. To skoro zní jako naše skládání origami!
To nás navádí k tomu zkusit definovat i nějakou obecnou redukci na stromech. Podobně, jako u seznamu, budeme mít návodou (redukční) funkci, která nám říká, jak stromy poskládat.
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b foldTree guide start = ft where ft Ext = start ft (Node l x r) = guide (ft l) x (ft r) -- Trik, jak zkrátit opakované psaní funkce se stejnými parametry size = foldTree (\l x r -> l + r + 1) 0 > size $ listToBST [1,1,2,3,5,5,3] 4
Cvičení: Napište funkci depth
pomocí foldTree
.
Cvičení: Napište funkci find
pomocí foldTree
. Jak bude efektivní?
Funkce foldTree
nám už stačí k tomu, abychom mohli libovolný strom převést na
seznam jeho prvků v infixovém pořadí.
treeList = foldTree (\l x r -> l ++ (x:r)) []
Cvičení: Napište funkce treeListPrefix
a treeListPostfix
, které strom
převedou na seznam v prefixovém nebo postfixovém pořadí prvků.
Třída Foldable, aneb udělejme si papír
Všimněme si, že pomocí treeList
můžeme nyní na strom použít libovolnou
funkci, která je definovaná přes foldr
nebo foldl
. Sice tím ztratíme
strukturu stromu, ale říká nám to něco jiného. Speciálně, když se vrátíme k
analogii s Origami, stromy jsou jen jiný druh papíru.
Z toho vyplývá, že seznam není jediná struktura, kterou můžeme redukovat.
Haskell s tímto samozřejmě počítá, a proto definuje třídu Foldable
. Aby byl
typ instancí třídy Foldable
, musí nadefinovat foldr
.
class Foldable f where foldr :: (a -> b -> b) -> b -> f a -> b
Typy typů, aneb přidáme úroveň meta
Při vysvětlování instanciování tříd jsme zatajili, že ještě existuje další metatypový systém nad typy, který popisuje počet parametrů typu. Narozdíl od toho běžného je však mnohem jednodušší.
Typ bez libovolného parametru je druhu (kind) *
. Pokud má typ nějaký parametr,
tak je jeho druh * -> *
. Tento druh pak říká, že typ bere parametr a vrací
jiný typ. Jak si bystřejší čtenáři povšimnou, i na druhy typů se aplikuje
Currying.
Pojďme se podívat na příkladech, jak se druhy typů chovají. Pro typ můžeme jeho
druh zjistit pomocí funkce :k
.
> :k Integer Integer :: * > :k Bool Bool :: * > :k Integer -> Bool Integer -> Bool :: * > :k [] [] :: * -> * > :k [Integer] [Integer] :: * > :k GeneralTree GeneralTree :: * -> * -> * > :k Tree Tree :: * -> * > :k Tree Integer Tree Integer :: *
Typové třídy pak mají taky svůj druh. Speciálně typová třída bere nějaký typ a
vrací nějaké omezení, třeba pro funkci. Pak třeba typová třída Eq
je druhu *
-> Constraint
. Pak pro a => b
, musí a
být právě druhu Constraint
. Z
toho hned vidíme, že Eq
bere typ bez parametrů a vrací omezení. Co to znamená
pro Foldable
?
> :k Foldable Foldable :: (* -> *) -> Constraint > :k Tree Tree :: * -> * > :k Foldable Tree Foldable Tree :: Constraint > :k (Eq Bool, Ord Int) (Eq Bool, Ord Int) :: Constraint > :k (Eq Bool, Ord Int) => Bool -> Int -> Bool (Eq Bool, Ord Int) => Bool -> Int -> Bool :: * > :k * * :: * -- Nebojte, více meta to nepůjde.
Stromy umíme vyjádřit jako Foldable
. Například už jen proto, že foldr
dokážeme provést nepřímo přes převod na seznam.
instance Foldable Tree where foldr = (foldr . treeList)
Toto sice funguje, ale zde spoléháme na to, že seznamy jsou Foldable
a
přidáváme si práci tím, že nejprve strom převedeme na seznam. Nešlo by to přeci
jen příměji?
Podívejme se, jak jsme převáděli strom na seznam a zkusme to poupravit. Externí vrchol jsme nahradili prázdným seznamem, místo toho tedy uvážíme startovní pozici. Vnitřní vrchol vypadal jako spojení více seznamů dohromady, toto spojení tedy nahradíme obecnou funkcí. Dohromady dostáváme:
instance Foldable Tree where foldr guide start Ext = start foldr guide start (Node l k r) = foldr guide (guide k (foldr guide start r)) l -- Nejprve zpracujeme pravý podstrom, ten zkombinujeme s vrcholem -- Výsledek zkombinujeme s levým podstromem > foldr (:) [] $ listToBST [3,1,4,1,5] [1,3,4,5] > sum $ listToBST [5,4,3,2,1] 15
Monády, aneb popisujeme sekvenční akce
Velmi důležitý koncept v Haskellu jsou monády, které popisují výpočty, které lze skládat dohromady. Monády nám pak umožní oddělit od sebe samotné složení akcí od jejich vyhodnocení. Jako další velmi důležitý efekt dostaneme možnost vytvoření výpočtů s vedlejšími účinky. Pokud chcete vědět, proč se takovým strukturám říká monády, můžete si projít teorii kategorií.
Díky monádám pak třeba můžeme popsat věci, které normálně nemáme k dispozici, jako interaktivita s uživatelem, vytváření náhodných generátorů, propagace chyb a další.
Každá monáda nám dává k dispozici dvě operace. První z nich vytvoří výpočet vracející danou hodnotu. Ta druhá je sekvenční skládání dvou výpočtů, kde ten druhý pracuje na základě hodnoty vypočítané prvním výpočtem. Obecně se ale nemůžeme jen tak podívat přímo na vypočtenou hodnotu, pouze právě na základě ní provést další výpočet.
S jednou monádou už jsme se setkali, speciálně o typ Maybe
. Vytvoření výpočtu
je vložení hodnoty do Just
a funkce andThen
je přesně sekvenční kombinace,
která reaguje na vnitřní hodnotu, pokud nějaká existuje.
Co vše ale obnáší vytvoření monády a co vše musíme udělat, abychom si monádu pořídili? Pojďme si tedy postupně vybudovat vlastnosti struktury, které potřebujeme k tomu, abychom došli k monádě. Všechny třídy, které zde ukážeme, jsou součástí standardní knihovny.
Jako příklad struktury budeme po celou dobu používat Maybe
a navíc tento typ,
který umožní rozlišovat mezi hodnotou a chybovým stavem.
data Result a = Error [String] | OK a deriving (Show)
Funktory
Mějme nějaký typ popisující nějaký kontejner, který do sebe umožňuje ukládat prvky. Na tento kontejner navíc můžeme poslat funkci, která každý prvek změní za jiný, čímž dostaneme nový kontejner. Definice funktoru je tudíž:
class Functor f where fmap :: (a -> b) -> f a -> f b > :k Functor Functor :: (* -> *) -> Constraint
Od funktorů očekáváme, že se chovají rozumně. Speciálně, fmap id
kontejner
nezmění a při skládání funkcí je jedno, zda je složíme před nebo po aplikaci
fmap
.
Pokud vám to nápadně připomíná seznamový map
, máte pravdu. Seznamy jsou
opravdu funktory. Konkrétně, pro seznamy je fmap
přímo map
.
A co naše typy Maybe
a Result
? I ty budou funktory. Pro oba typy při fmap
aplikujeme funkci pouze, pokud opravdu hodnotu obsahují, jinak necháme
Nothing
nebo chybu. Navíc, i stromy mohou být funktory.
instance Functor [] where fmap = map instance Functor Maybe where fmap _ Nothing = Nothing fmap f (Just x) = Just (f x) instance Functor Result where fmap _ e@(Error _) = e fmap f (OK x) = OK (f x) instance Functor Tree where fmap _ Ext = Ext fmap f (Node l x r) = Node (fmap f l) (f x) (fmap f r)
Protože fmap
bere funkci typu a -> b
, kde a
i b
může být cokoliv, musí
kontejner být parametrizován.
Proto nedává smysl, aby třeba Integer
byl funktor. Stejně tak, nemůžeme říct,
že konkrétní seznam Integer
ů je funktor, protože jej potenciálně nebudeme
moci převést třeba na seznam Bool
ů. Taktéž nemůže být funktor ani
parametrizovaný typ data T a = T (a -> Int)
, protože b
nemůže být obecné.
Cvičení: Kdy může být uspořádaná dvojice funktor? Existuje jediný způsob,
jak pro ní definovat fmap
?
Cvičení: Může být abstraktní typ, který reprezentuje uspořádanou množinu s vyhledáváním, vkládáním nebo nalezením následníka, funktor?
Kromě toho existují též operátory pracující s funktory. Všimněme si analogií s
$
, což je prostá aplikace funkce. Navíc, vzhledem k asociavitě ->
zprava i
vidíme, co tyto operátory skutečně provádí s funkcí:
(<$>) = fmap (<$) = fmap . const -- nahrazení všech prvků konstantou ($) :: (a -> b) -> ( a -> b) -- S funkcí nic neprovedeme (<$>) :: Functor f => (a -> b) -> (f a -> f b) -- Funkci pozvedneme na úroveň funktoru const :: b -> ( a -> b) -- Konstantu pozvedneme na funkci (<$) :: Functor f => b -> (f a -> f b) -- Konstantu pozvedneme na funkci úrovně funktoru > (*2) $ 3 6 > (*2) <$> Just 3 Just 6 > (*2) <$> Error ["Not an integer"] Error ["Not an integer"] > 5 <$ OK 3 OK 5 > 5 <$ Nothing Nothing > (*2) <$> [1,2,3] [2,4,6]
Aplikativní funktory
Možnost aplikovat funkci na každý prvek kontejneru je samo o sobě již celkem zajímavé. Potíž je, že ta funkce je omezená na jediný parametr a pracuje pouze na jednom kontejneru. Co kdybychom však chtěli umožnit kombinovat funktorové kontejnery pomocí aplikace funkce více parametrů podobně, jako třeba zkombinovat dvě čísla do jednoho součtem?
Konkrétněji, máme libovolnou funkci dvou hodnot a chtěli bychom ji převést na
funkci dvou kontejnerů, která je pomocí této funkce zkombinuje do nového
kontejneru funkčních hodnot. Toto pozvednutí zachytíme funkcí liftA2 :: (a ->
b -> c) -> (f a -> f b -> f c)
.
Pojďme se na liftA2
podivat trochu z jiného úhlu. Vzhledem k tomu, že
aplikace funkcí v Haskellu probíhá přes Currying, popíšeme, jak se nám chovají
binární funkce na aplikativních kontejnerech jinak:
Do fmap
vložíme funkci o dvou parametrech a kontejner splňující vlastnosti
funktoru. Tím dostaneme kontejner plný funkcí. Pak vezmeme druhý kontejner a
ten nějak zkombinujeme se vzniklým kontejnerem funkcí, které nějak aplikujeme
(proto aplikativní funktor). Jako výsledek vznikne nový kontejner. Tuto
kombinaci označíme operátorem (<*>)
.
Dále ještě budeme chtít funkci stylu liftA0 :: a -> f a
, která bere nulární
funkci (tedy hodnotu) a vloží ji do kontejneru. Takové funkci budeme říkat
pure
. Funkci liftA1
již máme, to je právě fmap
.
Takto jsme právě vytvořili třídu aplikativních funktorů. Jeji definice bude:
class Functor f => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c liftA2 f x y = f <$> x <*> y -- Pozorování: liftA2 id = (<*>)
Co to znamená z pohledu naších typů? Pokud máme v Maybe
nebo Result
uloženou funkci i hodnotu, můžeme ji zdárně aplikovat a výsledek dostaneme.
Pokud však jedno z toho není správná hodnota, nevrátíme nic či zřetězíme chyby.
instance Applicative Maybe where pure = Just Just f <*> Just x = Just (f x) _ <*> _ = Nothing instance Applicative Result where pure = OK OK f <*> OK x = OK (f x) Error e <*> OK _ = Error e OK _ <*> Error e = Error e Error ef <*> Error ex = Error (ef ++ ex) > liftA2 (+) (Just 2) (Just 3) Just 5 > Nothing <*> Just True <*> Just False Nothing > Error ["Function does not exist"] <*> Error ["Divided by zero"] Error ["Function does not exist", "Divided by zero"]
U aplikativních kontejnerů se nám pomalu začíná ukazovat sekvenční skládání
akcí. U typu Maybe
před každou další akcí zkontrolujeme, že něco máme. Typ
Result
je trochu zajímavější. Tam se nám při skládání akcí kumulují všechny
chyby, které v průběhu výpočtu nastaly.
O stromech víme, že to jsou funktory. Mohou být však aplikativní? Zde už začíná dost záviset na sémantice stromů a způsobem jejich kombinace. V tom nejobecnějším případě tedy stromy aplikativní nejsou.
Cvičení: Ukažte příklad, kdy mohou být stromy aplikativní.
Cvičení: Ukažte, že aplikativní struktury podporují aplikaci funkce o
libovolném počtu parametrů. Konkrétně, naprogramujte liftA3
.
A co seznamy? I ty jsou aplikativní. U těch operace <*>
dělá to, že vezme
každou funkci, tu provede na každý prvek druhého seznamu a všechny takto
vzniklé seznamy spojí dohromady. Funkce pure
je jednodušší, ta prostě vrátí
jednoprvkový seznam.
Cvičení: Naprogramujte <*>
na seznamech.
Cvičení: Pomocí vlastností aplikativního funktoru naprogramujte funkci vracející kartézský součin dvou seznamů.
Jako příklad funktoru, který jistě nemůže být aplikativní, můžeme uvážit typ
uspořádaných dvojic, kde fmap
mění druhou složku. Zde narazíme na to, že se
nám nepodaří napsat pure
, museli bychom totiž vytvořit z "ničeho" prvek typu
a
.
data Pair a b = Pair a b instance Functor (Pair a) where fmap f (Pair a b) = Pair a (f b) -- pure y = Pair (???) y
I aplikativní funktory mají určité sémantické vlastnosti, které musí splňovat. Většina z nich prostě říká, že by aplikace funkcí měla být rozumná.
Zatímco máme k dispozici pure
jakožto pozvednutí konstanty, tak opačný směr,
kdy tedy "vytahujeme" prvek z kontejneru, nedává smysl. Co máme vrátit, když
dostaneme Nothing
? Jakmile se něco do kontejneru dostane, už to z něj v
nejobecnějším případě nedostaneme. V některých příkladech si to ale můžeme
dovolit, viz fromJust
.
Od aplikativních funktorů k monádám
Podívejme se nyní na aplikativní funktory jako na nějaké černé skříňky, které
reprezentují sekvenční akce. Funkce pure
umožňuje nastartovat akci z
počáteční hodnoty. Dále fmap
umožňuje změnit chování akce. Nakonec <*>
umí
vzít dvě akce a sekvenčně je zřetězit.
Háček je, že <*>
umí pouze vzít akci a tu zřetězit s jinou. Nemůžeme zatím
akci provést, podívat se na její výsledky a na jejich základě vytvořit další
akci. Formálně tato operace odpovídá funkci bind :: (Applicative f) -> f a ->
(a -> f b) -> f b
, která svazuje výsledek akce s reakcí na něj. To je přesně
to, co jsme v úvodu slíbili od monád!
Monáda je tedy aplikativní funktor, jenž navíc podporuje právě funkci bind
,
kterou reprezentujeme operátorem >>=
.
class Applicative m => Monad m where return = pure (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b -- Sekvenčně spoj dvě akce, ale zahoď výsledek první z nich -- Pokud první akce měla vedlejší efekty, provedou se
Nyní si můžeme uvědomit, že Maybe
i Result
vlastně odpovídají akcím, které
mohou kdykoliv selhat. Pokud akce selže někdy v průběhu výpočtu, nemá smysl v
něm dále pokračovat. U Result
navíc propagujeme chybový stav.
Navíc, kdykoliv se můžeme podívat dovnitř kontejneru a vytáhnout si hodnotu v
něm. Pokud tam žádná hodnota není, tak zpropagujeme chybu. Jinak na bázi této
hodnoty můžeme pak pokračovat dál, nebo pokud je divná (třeba je hodnota
dělitel a dostali jsme nulu), můžeme skončit se selháním. To zní jako bind
,
že?
instance Monad Maybe where Nothing >>= _ = Nothing Just x >>= f = f x instance Monad Result where Error e >>= f = Error e OK x >>= f = f x -- Pro (>>) nad Maybe pak platí: -- Nothing >> _ = Nothing -- Just _ >> x = x -- Nad Result obdobně, jen se propaguje chyba half :: Integer -> Maybe Integer half x = if even x then Just (x `div` 2) else Nothing divSafe :: Integer -> Integer -> Result Integer divSafe x y = if y == 0 then Error ["Division by zero"] else OK $ x `div` y > return 6 >>= half Just 3 > return 6 >>= half >> return 100 Just 100 > return 5 >>= half Nothing > return 5 >>= half >> return 100 Nothing > Nothing >>= half Nothing > divSafe 9 3 >>= \x -> return 2*x+1 OK 7 > divSafe 4 0 >>= \x -> return 2*x+1 Error ["Division by zero"]
Monády jsou dokonce tak důležité, že pro práci s nimi existuje speciální do
syntaxe, která popisuje imperativní programování. Ukažme si příklad.
func x = do y <- half x -- Nechť y je polovina x let z = x + y -- Přiřaď do z součet x + y w <- half (x + z) -- Nechť w je polovina (x + z) half w -- Zkus, zda existuje polovina w return (x + y + z + w) -- Vrať součet všeho > func 1 Nothing -- Selže už první half x > func 2 Nothing -- Selhalo half (x+z) > func 4 Nothing -- Selhalo half w > func 8 Just 34 > (-) <$> func 8 <*> pure 4 Just 30 -- Stále můžeme využívat vlastnosti aplikativního funktoru
Stále je však do
syntaxe syntaktický cukr. Abychom lépe pochopili, co se
skutečně děje, přepsali jsme funkci nahoře pouze pomocí monadických operátorů.
func x = half x >>= \y -> let z = x + y in half (x + z) >>= \w -> half w >> return (x + y + z + w)
Na monády se podíváme blíže příště.