data Tree a = Leaf
deriving (Show)-- where Integer is the height (bottom = 0)
height Leaf = 0
height (Node n _ _ _) = n
insertFree index x Leaf = Just (Node index Leaf x Leaf)
insertFree _ x (Node level Leaf val right) = Just (Node level (Node (level-1) Leaf x Leaf) val right)
insertFree _ x (Node level left val Leaf) = Just (Node level left val (Node (level-1) Leaf x Leaf))
-- insertFree _ _ _ = Nothing
-- make balanced, binary tree (height diff is <= 1)
-- Note - I would've liked to have kept `foldTree` point-free,
-- but I'm not sure how to do that since I need `xs` for `treeHeight`
foldTree :: [a] -> Tree a
foldTree xs
= (foldingFn
. zip [0..]) xs
where foldingFn
= foldr (\
(i
, elem) acc
-> if (odd i
) then insertFreeOrLeft treeHeight
elem acc
else insertFreeOrRight treeHeight
elem acc
) Leaf
treeHeight = getBinTreeHt xs
-- get Binary Tree Height (used to start making the Tree)
-- insert where there's a Leaf, otherwise choose Left
insertFreeOrLeft
:: Integer -> a
-> Tree a
-> Tree a
insertFreeOrLeft index x Leaf = Node index Leaf x Leaf
insertFreeOrLeft _ x (Node level Leaf val right) = Node level (Node (level-1) Leaf x Leaf) val right
insertFreeOrLeft _ x (Node level left val Leaf) = Node level left val (Node (level-1) Leaf x Leaf)
insertFreeOrLeft _ x (Node level left val right) = Node level (insertFreeOrLeft (level-1) x left) val right
-- insert where there's a Leaf, otherwise choose Right
insertFreeOrRight
:: Integer -> a
-> Tree a
-> Tree a
insertFreeOrRight index x Leaf = Node index Leaf x Leaf
insertFreeOrRight _ x (Node level left val Leaf) = Node level left val (Node (level-1) Leaf x Leaf)
insertFreeOrRight _ x (Node level Leaf val right) = Node level (Node (level-1) Leaf x Leaf) val right
insertFreeOrRight _ x (Node level left val right) = Node level left val (insertFreeOrRight (level-1) x right)
layoutTree Leaf = [] -- wow, that was easy
layoutTree (Node _ left here right)
= indent
(layoutTree right
) ++ [show here
] ++ indent
(layoutTree left
)
main
= putStrLn $ prettyTree
$ foldTree
[0..127]