Haskell: A Hierarchy of Trees
module Tree where
class OrderedSet h where
insertOrdered :: Ord a => (h a, a) -> h a
class Tree h where
isEmptyTree ::
root
::
height
::
preOrder
::
successors
::
h
h
h
h
h
a
a
a
a
a
->
->
->
->
->
Bool
a
Integer
[a]
[h a]
height t = if isEmptyTree t then 0
else if length (successors t) == 0 then 1
else 1 + maximum (map height (successors t))
class (Tree h) => BinTree h where
left
:: h a -> h a
right
:: h a -> h a
inOrder
:: h a -> [a]
inOrder t = if isEmptyTree t then []
else inOrder(left t) ++ [root t] ++ inOrder(right t)
class (Tree h) => ArbTree h
{- koennte man weglassen -}
data StandBinTree a = EmptyBinTree
| Node(a, StandBinTree a, StandBinTree a)
instance Tree StandBinTree where
isEmptyTree(EmptyBinTree) = True
isEmptyTree(Node(_,_,_)) = False
root(EmptyBinTree) = error "root of empty tree"
root(Node(r, _, _)) = r
preOrder(EmptyBinTree) = []
preOrder(Node(root, left, right))
= root : preOrder(left) ++ preOrder(right)
successors(EmptyBinTree) = []
successors(Node(_, l, r)) = [l, r]
instance BinTree StandBinTree where
left(EmptyBinTree) = error "left of empty tree"
left(Node(_, l, _)) = l
right(EmptyBinTree) = error "right of empty tree"
right(Node(_, _, r)) = r
instance OrderedSet StandBinTree where
insertOrdered(EmptyBinTree,x) = Node(x, EmptyBinTree, EmptyBinTree)
insertOrdered(Node(root, left, right),x)
= if x < root then
Node(root, insertOrdered(left, x), right)
else if root < x then
Node(root, left, insertOrdered(right, x))
else Node(root, left, right)
data StandArbTree a = EmptyArbTree | ArbNode(a, [StandArbTree a])
newLeaf x = ArbNode(x, [])
-- gehoert eigentlich nach class Tree
instance Tree StandArbTree where
isEmptyTree(EmptyArbTree) = True
isEmptyTree(ArbNode(_,_)) = False
root(EmptyArbTree) = error "root of empty tree"
root(ArbNode(r, _)) = r
preOrder(EmptyArbTree) = []
preOrder(ArbNode(root, succs))
= root : (concatMap preOrder succs)
successors(EmptyArbTree) = []
successors(ArbNode(_, s)) = s
instance ArbTree StandArbTree

Conference dinner

here - Donald Danforth Plant Science Center

inv