home Grundlagen der Funktionalen Programmierung: Bäume Prof. Dr. Uwe Schmidt FH Wedel
Kapitelübersicht
Selbstdefinierte DatentypenInhaltsverzeichnisAuswertung arithmetischer Ausdrücke

Bäume

weiter
weiter

Listen implementiert als Bäume

Motivation
Eingebaute Haskell-Listen sind eine unsymmetrische Datenstruktur.
schlecht
Der Zugriff auf das erste Element der Liste ist in konstanter Zeit möglich,
der Zufriff auf das letzte nur in einer Zeit proportional zur Länge der Liste.
schlecht
Die Konkatenation zweier Listen benötigt eine Zeit proportional zur Länge der ersten Liste.
weiter
Verbesserung
Ein binärer Baum mit Information an den Blättern
 
data Tree a = Nil                     -- leerer Baum
            | Leaf a                  -- Blatt mit Information
            | Fork (Tree a) (Tree a)  -- binäre Verzweigung
weiter
Konsistenzbedingung
Nil nur als Wurzel, nicht als Teilbaum eines Fork-Knotens
 
invTree :: Tree a -> Bool
invTree Nil          = True
invTree (Leaf _x)    = True
invTree (Fork Nil r) = False
invTree (Fork l Nil) = False
invTree (Fork l r)   = invTree l && invTree r
weiter
Smarte Konstruktoren
zum Sicherstellen der Konsistenzbedingung
 
Hier: eigener Operator für das Konkatenieren von Bäumen
 
infixr 5 <++>                         -- wie ++
 
(<++>) :: Tree a -> Tree a -> Tree a
 
Nil <++> t2  = t2
t1  <++> Nil = t1
t1  <++> t2  = Fork t1 t2
 
 
cons :: a -> Tree a -> Tree a
cons x t = Leaf x <++> t
 
snoc :: Tree a -> a -> Tree a
snoc t x = t <++> Leaf x
?
Laufzeit von <++>?
?
Laufzeit von cons und snoc?
gut
Die Verwendung von <++> anstatt Fork garantiert die Konsistenz per Konstruktion
gut
Symmetrie in der Datenstruktur
==>
Symmetrie in den Algorithmen (cons und snoc)
weiter
Transformation
Baum ==> Liste
 
flatten :: Tree a -> [a]
 
flatten Nil        = []
flatten (Leaf x)   = [x]
flatten (Fork l r) = flatten l ++ flatten r
merke
Datenstruktur bestimmt die Struktur der Algorithmen
schlecht
Laufzeit wird bestimmt durch die Laufzeit von ++
schlecht
Laufzeit nicht linear abhängig von der Anzahl Elemente im Baum
?
Verbesserung möglich?
weiter
Transformation
Liste ==> Baum
1. Versuch
naiv
 
build0 :: [a] -> Tree a
 
build0 [] = Nil
build0 (x : xs) = Leaf x <++> build0 xs
 
==>
 
build0 = foldr (λ x t -> Leaf x <++> t) Nil
gut
Laufzeit ist linear abhängig von der Anzahl der Elemente
schlecht
Struktur des Baumes ist isomorph zur Struktur der Liste
schlecht
Laufzeit des Zugriffs auf das letzte Element wie bei Listen
weiter
2. Versuch
Ausgewogener Baum
 
build :: [a] -> Tree a
 
build []  = Nil
build [x] = Leaf x
build xs  = Fork (build l) (build r)
  where
   (l, r) = splitAt (length xs `div` 2) xs
gut
Ausgewogener Baum
gut
Alle Pfade von der Wurzel zu einem Blatt unterscheiden sich in der Länge höchstens um 1
gut
Die Anzahl der Elemente in den linken und rechten Teilbäumen unterscheiden sich höchstens um 1
gut
Laufzeiten der Zugriffe auf das erste und das letzte Element sind gleich
schlecht
Die Laufzeit von build hängt nicht linear ab von der Anzahl der Elemente
weiter
3. Versuch
Ausgewogener Baum
 
build2 :: [a] -> Tree a
 
build2 [] = Nil
build2 xs = build' (map Leaf xs)
  where
    build' [t] = t
    build' ts  = build' (merge ts)
 
    merge (t1 : t2 : ts) = Fork t1 t2 : merge ts
    merge ts             = ts
gut
Ausgewogener Baum
merke
Hier gilt ein etwas schwächeres Ausbalacier-Kriterium
gut
Alle Pfade von der Wurzel zu einem Blatt haben eine minimale Länge
gut
Die Laufzeit von build2 hängt linear ab von der Anzahl der Elemente
weiter
Selektor-Funktionen
analog zu head, tail, last und init
 
head :: Tree -> a
 
head Nil        = error "head with Nil"
head (Leaf x)   = x
head (Fork l r) = head l
 
last :: Tree -> a
 
last Nil        = error "last with Nil"
last (Leaf x)   = x
last (Fork l r) = last r
 
 
tail :: Tree a -> Tree a
 
tail Nil        = error "tail: empty tree"
tail (Leaf _x)  = Nil
tail (Fork l r) = tail l <++> r
 
 
init :: Tree a -> Tree a
 
init Nil        = error "init: empty tree"
init (Leaf _x)  = Nil
init (Fork l r) = l <++> init r
merke
Symmetrie in Tree
==>
Symmetrie von head und last und tail und init
weiter
merke
Laufzeit ist proportional zur Länge des Pfades von der Wurzel zum Blatt
merke
alle vier Funktionen sind partiell definiert
merke
Ähnlichkeiten im Code, also Abstrahieren!
weiter
Aufspalten
in erstes/letztes Element und Rest/Anfangsstück
 
viewL :: Tree a -> Maybe (a, Tree a)
 
viewL Nil       = Nothing
viewL (Leaf x)  = Just (x, Nil)
viewL (Fork l r)= Just (x, r1 <++> r)
                  where
                    Just (x, r1) = viewL l
 
viewR :: Tree a -> Maybe (Tree a, a)
 
viewR Nil       = Nothing
viewR (Leaf x)  = Just (Nil, x)
viewR (Fork l r)= Just (l1 <++> l, x)
                  where
                    Just (l1, x) = viewR r
weiter
gut
head, last, tail, init, safeHead, safeLast, safeTail und safeInit sind alle aus viewL und viewR ableitbar
 
head = maybe (error "head with Nil") fst . viewL
last = maybe (error "last with Nil") snd . viewR
tail = maybe (error "tail with Nil") snd . viewL
init = maybe (error "init with Nil") fst . viewR
 
safeHead = mapMaybe fst . viewL
safeLast = mapMaybe snd . viewR
safeTail = mapMaybe snd . viewL
safeInit = mapMaybe fst . viewR
weiter
mapTree
Verarbeiten aller Elemente eines Baumes unabhängig von ihrer Position
 
mapTree :: (a -> b) -> Tree a -> Tree b
 
mapTree f Nil        = Nil
mapTree f (Leaf x)   = Leaf (f x)
mapTree f (Fork l r) = mapTree f l `Fork` mapTree f r
weiter
merke
map, mapMaybe und mapTree sehr ähnlich!
merke
Abstrahieren und die map-Funktionen überladen
weiter
Functor-Klasse
für alle Datentypen, für die eine map-Funktion definiert werden kann
 
class Functor f where               -- vordefiniert
  fmap :: (a -> b) -> f a -> f b
 
instance Functor [] where           -- vordefiniert
  fmap = map
 
instance Functor Maybe where        -- vordefiniert
  fmap = mapMaybe
 
instance Functor Tree where
  fmap = mapTree
merke
Functor ist eine Klasse für Typkostruktoren mit einem Parameter, nicht für konkrete Typen
merke
fmap ist die überladene Funktion, da der Name map schon für Listen verwendet wird
weiter
Gesetzte
die für alle Instanzen gelten müssen
 
fmap id = id
 
fmap f . fmap g = fmap (f . g)
weiter
Filtern
von Bäumen analog zum Filtern von Listen
 
filterTree :: (a -> Bool) -> Tree a -> Tree a
 
filterTree p Nil        = Nil
filterTree p t@(Leaf x)
    | p x               = t
    | otherwise         = Nil
filterTree p (Fork l r) = filterTree p l <++> filterTree p r
 
-- NOT:
 
-- filterTree p (Fork l r) = filterTree p l `Fork` filterTree p r
weiter
Falten
von Bäumen analog zum Falten (foldr) von Listen
Beispiele
sumTree :: Num a => Tree a -> a
 
sumTree Nil        = 0                        -- c  = 0
sumTree (Leaf x)   = x                        -- f  = id
sumTree (Fork l r) = sumTree l + sumTree r    -- op = +
 
 
size :: Tree a -> Int
 
size Nil        = 0                           -- c  = 0
size (Leaf _)   = 1                           -- f  = const 1
size (Fork l r) = size l + size r             -- op = +
 
 
minpath :: Tree a -> Int
 
minpath Nil        = 0
minpath (Leaf _)   = 1
minpath (Fork l r) = (minpath l `min` minpath r) + 1
 
maxpath :: Tree a -> Int
 
maxpath Nil        = 0
maxpath (Leaf _)   = 1
maxpath (Fork l r) = (maxpath l `max` maxpath r) + 1
 
 
flatten :: Tree a -> [a]
 
flatten Nil        = []                       -- c  = []
flatten (Leaf x)   = [x]                      -- f  = λ x -> [x]
flatten (Fork l r) = flatten l ++ flatten r   -- op = ++
merke
Es gibt drei Stellen, an denen die Algorithmen sich unterscheiden
merke
Eine fold-Funktion benötigt also drei zusätzliche Parameter
.1
Das Resultat für den leeren Baum
.2
Eine 1-stellige Funktion zum Verarbeiten eines Blattes
.3
Eine 2-stellige Funktion zum Kombinieren der Resultate der verarbeiteten Teilbäume
weiter
fold :: (b -> b -> b) -> (a -> b) -> b ->
        Tree a -> b
 
fold op f c Nil        = c
fold op f c (Leaf x)   = f x
fold op f c (Fork l r) = fold op f c l `op` fold op f c r
weiter
Anwendungen
sumTree :: Num a => Tree a -> a
sumTree = fold (+) id 0
 
size  :: Tree a -> Int
size  = fold (+) (const 1) 0
 
minpath :: Tree a -> Int
minpath = fold (λ x y -> x `min` y + 1) (const 1) 0
 
maxpath :: Tree a -> Int
maxpath = fold (λ x y -> x `max` y + 1) (const 1) 0
 
flatten :: Tree a -> [a]
flatten = fold (++) (λ x -> [x]) []
 
invTree :: Tree a -> Bool
invTree Nil = True
invTree t   = fold (&&) (const True) False t
 
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f = fold Fork (Leaf . f) Nil
 
filterTree :: (a -> Bool) -> Tree a -> Tree a
filterTree p = fold (<++>) f Nil
  where
    f x | p x       = Leaf x
        | otherwise = Nil
weiter
Verbesserung
der fold-Funktion
 
fold :: (b -> b -> b) -> (a -> b) -> b ->
        Tree a -> b
 
fold op f c = go
  where
    go Nil        = c
    go (Leaf x)   = f x
    go (Fork l r) = go l `op` go r
weiter
gut
Die zusätzlichen drei Parameter müssen in den rekursiven Funktionen nicht mit durchgeschleift werden
gut
Laufzeit: Funktionsrümpfe können an Aufrufstelle eingesetzt werden
 
sumTree = go
  where
    go Nil        = 0
    go (Leaf x)   = id x
    go (Fork l r) = go l + go r
effizientes flatten
mit einer Laufzeit proportional zur Anzahl der Elemente im Baum
 
flatten :: Tree a -> [a]
flatten = go []
  where
    go acc Nil        = acc
    go acc (Leaf x)   = x : acc
    go acc (Fork l r) = go (go acc r) l
Idee
der Baum wird einmal von rechts nach links traversiert und die Elemente schrittweise bei der Verarbeitung der Blätter vorne an den Akkumulator angehängt
weiter

Beispiele zum Kapitel

   1module Tree2
   2where
   3
   4import Prelude hiding ( head, tail
   5                      , last, init
   6                      )
   7import qualified Prelude as P
   8import ShowTree
   9
  10data Tree a = Nil
  11            | Leaf a
  12            | Fork (Tree a) (Tree a)
  13            deriving (Show)
  14
  15-- invariant:
  16-- Nil only as root
  17
  18invTree :: Tree a -> Bool
  19invTree Nil          = True
  20invTree (Leaf _x)    = True
  21invTree (Fork Nil r) = False
  22invTree (Fork l Nil) = False
  23invTree (Fork l r)   = invTree l && invTree r
  24
  25-- slow flatten
  26
  27flatten :: Tree a -> [a]
  28flatten Nil        = []
  29flatten (Leaf x)   = [x]
  30flatten (Fork l r) = flatten l ++ flatten r
  31
  32-- fast flatten
  33
  34flatten1 :: Tree a -> [a]
  35flatten1 t = go t []
  36  where
  37    go Nil        acc = acc
  38    go (Leaf x)   acc = x : acc
  39    go (Fork l r) acc = (go l . go r) acc
  40
  41flatten1' :: Tree a -> [a]
  42flatten1' t = go t []
  43  where
  44    go Nil        = id
  45    go (Leaf x)   = (x :)
  46    go (Fork l r) = go l . go r
  47
  48-- simple minded build, builds lists as trees
  49
  50build0 :: [a] -> Tree a
  51build0 xs = foldr (<++>) Nil (map Leaf xs)
  52
  53-- smart but a bit slow build due to splitAt and length
  54
  55build1 :: [a] -> Tree a
  56build1 []  = Nil
  57build1 [x] = Leaf x
  58build1 xs  = Fork (build1 l) (build1 r)
  59  where
  60    (l, r) = splitAt (length xs `div` 2) xs
  61
  62-- smart and fast build
  63
  64build2 :: [a] -> Tree a
  65build2 xs
  66  | null xs   = Nil
  67  | otherwise = build' (map Leaf xs)
  68  where
  69    build' [t] = t
  70    build' ts  = build' (merge ts)
  71
  72    merge (t1 : t2 : ts) = Fork t1 t2 : merge ts
  73    merge ts             = ts
  74
  75-- some test trees
  76
  77t0, t1, t2, t100 :: Tree Int
  78t0   = build0 [1..9]
  79t1   = build1 [1..9]
  80t2   = build2 [1..9]
  81t100 = build1 [1..100]
  82
  83-- list like functions for trees
  84
  85head :: Tree a -> a
  86head Nil         = error "head: empty list"
  87head (Leaf x)    = x
  88head (Fork l _r) = head l
  89
  90last :: Tree a -> a
  91last Nil         = error "last: empty list"
  92last (Leaf x)    = x
  93last (Fork _l r) = last r
  94
  95-- <++> is ++ for trees
  96
  97infixr 5 <++>
  98(<++>) :: Tree a -> Tree a -> Tree a
  99Nil <++> t2  = t2
 100t1  <++> Nil = t1
 101t1  <++> t2  = Fork t1 t2
 102
 103cons :: a -> Tree a -> Tree a
 104cons x t = Leaf x <++> t
 105
 106snoc :: Tree a -> a -> Tree a
 107snoc t x = t <++> Leaf x
 108
 109tail :: Tree a -> Tree a
 110tail Nil        = error "tail: empty tree"
 111tail (Leaf _x)  = Nil
 112tail (Fork l r) = tail l <++> r
 113
 114init :: Tree a -> Tree a
 115init Nil        = error "init: empty tree"
 116init (Leaf _x)  = Nil
 117init (Fork l r) = l <++> init r
 118
 119viewL :: Tree a -> Maybe (a, Tree a)
 120viewL Nil       = Nothing
 121viewL (Leaf x)  = Just (x, Nil)
 122viewL (Fork l r)= Just (x, r1 <++> r)
 123                  where
 124                    Just (x, r1) = viewL l
 125
 126viewR :: Tree a -> Maybe (Tree a, a)
 127viewR Nil       = Nothing
 128viewR (Leaf x)  = Just (Nil, x)
 129viewR (Fork l r)= Just (l1 <++> l, x)
 130                  where
 131                    Just (l1, x) = viewR r
 132
 133mapTree :: (a -> b) -> Tree a -> Tree b
 134mapTree f Nil        = Nil
 135mapTree f (Leaf x)   = Leaf (f x)
 136mapTree f (Fork l r) = Fork (mapTree f l) (mapTree f r)
 137
 138instance Functor Tree where
 139  fmap = mapTree
 140
 141filterTree :: (a -> Bool) -> Tree a -> Tree a
 142filterTree p Nil        = Nil
 143filterTree p (Leaf x)
 144    | p x               = Leaf x
 145    | otherwise         = Nil
 146filterTree p (Fork l r) = filterTree p l <++> filterTree p r
 147
 148-- nice try:
 149-- filterTree p (Fork l r) = filterTree p l `Fork` filterTree p r
 150
 151sumTree :: Num a => Tree a -> a
 152sumTree Nil        = 0
 153sumTree (Leaf x)   = x
 154sumTree (Fork l r) = sumTree l + sumTree r
 155
 156size :: Tree a -> Int
 157size Nil        = 0
 158size (Leaf _)   = 1
 159size (Fork l r) = size l + size r
 160
 161minpath :: Tree a -> Int
 162minpath Nil        = 0
 163minpath (Leaf _)   = 1
 164minpath (Fork l r) = (minpath l `min` minpath r) + 1
 165
 166maxpath :: Tree a -> Int
 167maxpath Nil        = 0
 168maxpath (Leaf _)   = 1
 169maxpath (Fork l r) = (maxpath l `max` maxpath r) + 1
 170
 171fold :: (b -> b -> b) -> (a -> b) -> b ->
 172        Tree a -> b
 173fold op f c Nil        = c
 174fold op f c (Leaf x)   = f x
 175fold op f c (Fork l r) = fold op f c l `op` fold op f c r
 176
 177fold' :: (b -> b -> b) -> (a -> b) -> b ->
 178         Tree a -> b
 179fold' op f c = fold''
 180  where
 181    fold'' Nil        = c
 182    fold'' (Leaf x)   = f x
 183    fold'' (Fork l r) = fold'' l `op` fold'' r
 184
 185sumTree' :: Num a => Tree a -> a
 186sumTree' = fold (+) id 0
 187
 188size' :: Tree a -> Int
 189size' = fold (+) (const 1) 0
 190
 191minpath' :: Tree a -> Int
 192minpath' = fold (\ x y -> x `min` y + 1) (const 1) 0
 193
 194maxpath' :: Tree a -> Int
 195maxpath' = fold (\ x y -> x `max` y + 1) (const 1) 0
 196
 197notNil :: Tree a -> Bool
 198notNil = fold (&&) (const True) False
 199
 200-- slow flatten with fold
 201
 202flatten' :: Tree a -> [a]
 203flatten' = fold (++) (\ x -> [x]) []
 204
 205-- fast flatten, O(n)
 206
 207flatten'' :: Tree a -> [a]
 208flatten'' = go []
 209  where
 210    go acc Nil = acc
 211    go acc (Leaf x) = x : acc
 212    go acc (Fork l r) = go (go acc r) l
 213
 214-- mapTree with fold, like map for lists with foldr
 215
 216mapTree' :: (a -> b) -> Tree a -> Tree b
 217mapTree' f = fold Fork (Leaf . f) Nil
 218
 219-- --------------------
 220--
 221-- conversion of trees into pseudo graphics
 222
 223showTree :: Show a => Tree a -> String
 224showTree = formatStringNTree . toNTree
 225  where
 226    toNTree Nil        = NTree "Nil" []
 227    toNTree (Leaf x)   = NTree ("Leaf " ++ show x) []
 228    toNTree (Fork l r) = NTree "Fork" [toNTree l, toNTree r]
 229
 230-- formatted print of trees
 231printTree :: Show a => Tree a -> IO ()
 232printTree = putStrLn . showTree
 233
 234-- --------------------
weiter

Die Quellen

Tree2.hs
ShowTree.hs
SeitenanfangKapitelübersicht
Selbstdefinierte DatentypenInhaltsverzeichnisAuswertung arithmetischer Ausdrücke
Letzte Änderung: 08.01.2020
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel