Fifth group session

Tree.hs

-- data IntTree = IntLeaf Int
--              | IntBranch IntTree IntTree
--   deriving Show
-- IntLeaf   :: Int -> IntTree
-- IntBranch :: IntTree -> IntTree -> IntTree

intTree1 :: IntTree
intTree1 = Branch (Branch (Leaf 21)
                          (Leaf 5))
                  (Branch (Leaf 20)
                          (Leaf 14))

smallestTree :: IntTree
smallestTree = Leaf 0

-- linear in Anzahl der Blaetter
sumTreeAcc :: IntTree -> Int
sumTreeAcc tree = sumTreeAcc' 0 tree
 where
  sumTreeAcc' :: Int -> IntTree -> Int
  sumTreeAcc' acc (Leaf x)     = acc + x
  sumTreeAcc' acc (Branch l r) =
    sumTreeAcc' (sumTreeAcc' acc l) r

mirrorTree :: Tree a -> Tree a
mirrorTree (Leaf x)     = Leaf x
mirrorTree (Branch l r) = Branch (mirrorTree r)
                                 (mirrorTree l)

data Tree a = Leaf a | Branch (Tree a) (Tree a)
  deriving Show
type IntTree = Tree Int -- Typsynonym, Abkuerzung

-- im worst-case quadratisch in der Anzahl der Blaetter
treeToList :: Tree a -> [a]
treeToList (Leaf x)     = [x]
treeToList (Branch l r) = treeToList l ++ treeToList r

-- linear in Anzahl der Blaetter
sumTree :: IntTree -> Int
sumTree (Leaf x)     = x
sumTree (Branch l r) = sumTree l + sumTree r

-- own (++) version
-- linear in der Laenge der ersten Liste
append :: [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

----- Funny stuff with lists
maybePlus :: Maybe Int -> Int -> Maybe Int
maybePlus m x = case m of
                Nothing -> Nothing
                Just v  -> Just (v+x)

indexOf :: [Int] -> Int -> Maybe Int
indexOf []     _ = Nothing
indexOf (x:xs) y
  | x == y    = Just 0
  | otherwise = maybePlus (indexOf xs y) 1