playing with trees

trees.hs

data Tree a = Node a (Tree a) (Tree a) | Nil
  deriving Show

treeDown :: (Tree a -> Tree a -> a) -> [a] -> Int -> (Tree a, [a])
treeDown fn [] _ = (Nil, [])
treeDown fn (x:xs) 0 = (Node x Nil Nil, xs)
treeDown fn xs n =
  let (left, xs') = treeDown fn xs (n - 1)
      (right, rem) = treeDown fn xs' (n - 1)
  in  (Node (fn left right) left right, rem)

treeUp :: (Tree a -> Tree a -> a) -> [a] -> Int -> Tree a -> Tree a
treeUp fn [] n left = left
treeUp fn (x:xs) 0 left =
  treeUp fn xs 1 (Node x Nil Nil)

treeUp fn xs n left =
  let (right, rem) = treeDown fn xs (n - 1)
      up = Node (fn left right) left right
  in treeUp fn rem (n + 1) up

treeFromList :: (Tree a -> Tree a -> a) -> [a] -> Tree a
treeFromList fn xs = treeUp fn xs 0 Nil

getVal :: Tree a -> a -> a
getVal Nil def = def
getVal (Node x _ _) def = x

main =
  let add left right = getVal left 0 + getVal right 0
  in print $ treeFromList add [1,2,3,4,5,6,7,8]