Haskell - stromy a obecný fold

Kdo to ještě neuhodl, tak celé naše povídání o typech vede k tomu, abychom si nadefinovali vlastní binární strom.

data Strom a = Nil | Uzel (Strom a) a (Strom a) deriving (Show)

Strom tedy je buď Nil, nebo Uzel, který obsahuje dva podstromy a jednu hodnotu typu a.

Teď by se nám moc hodilo napsat si binární vyhledávací strom. Začneme napřed přidáním do stromu.

pridej :: Ord a => Strom a -> a -> Strom a
pridej Nil y                        = Uzel Nil y Nil
pridej (Uzel x b y) z   | z < b     = Uzel (pridej x z) b y
                        | otherwise = Uzel x b (pridej y z)

Ted už je jednoduché převést seznam na strom.

seznamNaBST :: Ord a => [a] -> Strom a
seznamNaBST = foldl pridej Nil

Viděli jsme, že pro práci se seznamy je velmi vhodné mít funkci map. Napišme si podobnou funkci i pro stromy.

treeMap :: (a -> b) -> Strom a -> Strom b
treeMap _ Nil           = Nil
treeMap f (Uzel l u p)  = Uzel (treeMap f l) (f u) (treeMap f p)

Vraťme se na chvíli k seznamům, a zamysleme se nad tím, co vlastně jsou. Můžeme si napsat vlastní seznam.

data Seznam a = SNil | Cons a (Seznam a) deriving Show

SNil nám označuje prázdný seznam, Cons a (Seznam a) je konstruktor, který spojuje jeden prvek se seznamem (v Haskellu (:)).

Aby se nám lépe s naším seznamem pracovalo, napišme si funkci, která převádí Haskellovský seznam na ten náš.

listNaSeznam :: [a] -> Seznam a
listNaSeznam = foldr Cons SNil

Definice je tak snadná, protože jen potřebujeme nahradit (:) za Cons a [] za náš SNil.

Důvod, proč tuhle odbočku děláme, je, abychom si ukázali, jak vypadá foldr na tomhle seznamu.

mujFoldr :: (a -> b -> b) -> b -> Seznam a -> b
mujFoldr _ fNil SNil            = fNil
mujFoldr fCons fNil (Cons x xs) = fCons x (mujFoldr fCons fNil xs)

Pomocí malého triku můžeme funkci zjednodušit. Funkce g tady zastupuje mujFoldr2 fCons fNil a tím si ušetříme opisování parametrů.

mujFoldr2 :: (a -> b -> b) -> b -> Seznam a -> b
mujFoldr2 fCons fNil = g where
                            g SNil          = fNil
                            g (Cons x xs)   = fCons x (g xs)

Tady je důležité si uvědomit, co ta funkce přesně dělá. Podívá se na oba datové konstruktory našeho seznamu (SNil a Cons) a nahradí je voláním nějaké funkce, která má stejný typ, jako daný konstruktor.

Zkusme tedy napsat fold pro stromy. V tomto případě máme opět dva konstruktory - Nil a Uzel a b c. Budeme tedy také potřebovat dvě funkce. Jedna z nich bude nulární a bude říkat, čím se má nahradit Nil. Druhá bude mít tři parametry, a bude říkat, co se má stát s každým uzlem. Výsledný typ funkce treeFold tedy bude:

treeFold :: (a -> b -> a -> a) -> a -> Strom b -> a
treeFold _      fNil Nil            = fNil
treeFold fUzel  fNil (Uzel l u p)   = fUzel (treeFold fUzel fNil l) u (treeFold fUzel fNil p)

Tahle definice foldu je trochu moc ukecaná, dá se zase zkrátit stejným trikem jako u seznamu.

treeFold2 :: (a -> b -> a -> a) -> a -> Strom b -> a
treeFold2 fUzel fNil =  g where
                            g Nil           = fNil
                            g (Uzel l u p)  = fUzel (g l) u (g p)

Porovnejte tyto dva foldy. Co mají společného? Oba nahrazuji všechny datové konstruktory svého typu voláním nějaké funkce. Pokud budete tedy chtít napsat fold pro nějaký vlastní typ, stačí udělat to samé.

Se stromovým foldem se zase dá dělat spousta zábavných věcí. Například je úplně jednoduché vypsat strom v prefixovém zápisu.

prefixBSTnaSeznam :: Strom a -> [a]
prefixBSTnaSeznam = treeFold (\la u pa -> la ++ (u:pa)) []

Co ta funkce dělá? Nahradí Nil prázdným seznamem, a potom má vlastně dva akumulátory, jeden obsahuje levou část, druhý pravou. Funkce je oba vezme a spoji je s prvkem v aktuálním uzlu.

Zkuste sami napsat infixovou a postfixovou variantu tohoto převodu.

Jak byste nadefinovali strom, který může reprezentovat aritmetický výraz s binárními operacemi?

Můžeme si napsat vlastní show funkci, která bude převádět Strom na String. Typová třída Show nám takovou funkci nadefinuje sama (když použijeme deriving Show), nebo si ji můžeme napsat sami, jako níže. Není možné oba způsoby kombinovat, proto definujeme nový typ stromu StromS.

Funkce není nijak extra, kreslí strom zleva doprava, čím dále vpravo číslo je, tím je hlouběji ve stromě.

data StromS a = NilS | UzelS (StromS a) a (StromS a)

showTree :: Show a => StromS a -> [String]
showTree (NilS) = []
showTree (UzelS l u p) = map (\x -> "   " ++ x) ((showTree p) ++ [show u] ++ (showTree l))

instance Show a => Show (StromS a) where
    show t = unlines (showTree t)