Kapitel 1: Haskell in einer Nußschale

hugs BinTree
ghc -c BinTree.lhs

> module BinTree
> where
> import Prelude hiding (splitAt)

Binärbäume.

> data Tree lab                 =  Empty | Node (Tree lab) lab (Tree lab)
>                                  deriving (Show, Read)
>
> type IntTree                  =  Tree Int

Beachte: um Bäume ausgeben zu können, ist der Zusatz
deriving (Show, Read)| nötig.

> atree                         :: IntTree
> atree                         =  Node (Node Empty 2 Empty) 5 Empty

> insert                        :: (Ord lab) => lab -> Tree lab -> Tree lab
> insert a Empty                =  Node Empty a Empty
> insert a (Node l b r)         =  if a <= b then Node (insert a l) b r
>                                            else Node l b (insert a r)

> big                           :: Int -> IntTree
> big n                         =  Node (big (2 * n)) n (big (2 * n + 1))

> prune                         :: Int -> Tree lab -> Tree lab
> prune 0 t                     =  Empty
> prune (n + 1) Empty           =  Empty
> prune (n + 1) (Node l a r)    =  Node (prune n l) a (prune n r)


> delete                        :: (Ord lab) => lab -> Tree lab -> Tree lab
> delete a Empty                =  Empty
> delete a (Node l b r)
>     | a < b                   =  Node (delete a l) b r
>     | a == b                  =  join l r
>     | otherwise               =  Node l b (delete a r)

> join                          :: Tree lab -> Tree lab -> Tree lab
> join Empty r                  =  r
> join (Node ll a lr) r         =  let (b, t) = split ll a lr in  Node t b r

> split                         :: Tree lab -> lab -> Tree lab -> (lab, Tree lab)
> split l a Empty               =  (a, l)
> split l a (Node rl b rr)      =  let (c, t) = split rl b rr in  (c, Node l a t)

Beispielausdrücke:

atree
insert 7 atree
delete 7 atree
delete 2 atree
foldr insert Empty [1 .. 10]
prune 2 (big 1)
prune 10 (big 1)

Lösung der Aufgabe 11.

> inorder                       :: Tree a -> [a]
> inorder Empty                 =  []
> inorder (Node l a r)          =  inorder l ++ a : inorder r

> build                         :: [a] -> Tree a
> build []                      =  Empty
> build (a : x)                 =  let (y, z) = splitAt (length x `div` 2) x
>                                  in  Node (build y) a (build z)

> splitAt                       :: Int -> [a] -> ([a], [a])
> splitAt 0 x                   =  ([], x)
> splitAt (n + 1) []            =  ([], [])
> splitAt (n + 1) (a : x)       =  let (y, z) = splitAt n x in (a : y, z)