Václav Končický

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ě.