I wrote a function, which takes a list of Integers, and then makes a balanced binary tree.
Please critique it. I'd like to know know how to make it more concise and idiomatic.
-- Note that the Integer represents the height of the Tree
data Tree a = Leaf
| Node Integer (Tree a) a (Tree a)
deriving (Show)-- where Integer is the height (bottom = 0)
-- 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)
getBinTreeHt :: [a] -> Integer
getBinTreeHt = floor . (logBase 2) . fromIntegral . length
-- 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)
Testing
*Main> foldTree "ABC"
Node 1 (Node 0 Leaf 'B' Leaf) 'C' (Node 0 Leaf 'A' Leaf)
*Main> foldTree "ABCDE"
Node 2 (Node 1 (Node 0 Leaf 'B' Leaf) 'D' Leaf) 'E' (Node 1 Leaf 'C' (Node 0 Leaf 'A' Leaf))
foldTreereturns linear depth. Just runfoldTree [0 .. 15], you will see negative heights. – abuzittin gillifirca Sep 29 '14 at 15:03foldTree [0 .. 15]. Output contains these nodes :(Node 1 Leaf 6 Leaf)(Node (-1) Leaf 0 Leaf)clearly height difference between these leaves is (1 - (-1)) = 2. (>1, hence unbalanced). – abuzittin gillifirca Sep 29 '14 at 15:10