Geevarghese Philip wrote:
I am trying to learn Haskell. As an exercise, I wrote a function to create a binary tree in level-order. I am attaching the code. I am sure there are a number of places where the code could be improved. Could you please point these out?
I'll try.
Thanks, Philip
insert :: Eq a => Tree a -> a -> Tree a insert tree x = if tree == Empty then Tree x Empty Empty else if (left tree) == Empty then Tree (rootNode tree) (Tree x Empty Empty) (right tree) [...]
you can use pattern matching to your advantage, to avoid if-s and comparisons (you can get rid of the Eq requirement that way) insert (Empty x) = Tree x Empty Empty insert (Tree root Empty rtree) = Tree root (Tree x Empty Empty) rtree ... insert ... | countNodes x <= countNodes y = ... | otherwise = ...
------------------------------------------------------------------------------ Use insert to create a tree from a sequence. ------------------------------------------------------------------------------
createTree :: Eq a => [a] -> Tree a createTree [] = Empty createTree (x:xs) = foldl insert (insert Empty x) xs
createTree xs = foldl insert Empty xs works just as well. Here are two algorithmic ideas: 1. It's possible to avoid the counting if you create a function that inserts multiple values at once, walking the nodes from left to right. -- walk tree from left to right and insert nodes at the next -- level as long as there are elements in the list left; -- keep the rest of the tree unmodified. insertLevel :: Tree a => [a] -> Tree a -> ([a], Tree a) insertLevel [] t = t insertLevel (x:xs) Empty = (Tree x Empty Empty, xs) insertLevel xs (Tree node ltree rtree) = ... Then use this function iteratively starting with an empty tree, until the whole list is consumed. 2. It's possible to build the tree from bottom up. This works, as follows: 1. split the given list into levels (that is, lists of length 2^n starting with n=0. The last, lowest level may be incomplete.) 2. convert the lowest level into singleton trees. Call the result the processed list, and mark the lowest level as processed. 3. For each unprocessed level, starting with the lowest, do: Walk through this level and the processed list simultaneously, combining one element from the level and two elements from the processed list and combining them into a tree Node. When the level is exhausted, we take empty trees to fill it up. The result is the new processed list. 4. Now the processed list is either empty - in which case we return an empty tree, or a list that contains a single tree, in which case we return that. Example: (I write E for Empty) input = [1,2,3,4,5,6,7,8,9,10] 1. levels = [[1],[2,3],[4,5,6,7],[8,9,10]] 2. processed = [Tree 8 E E, Tree 9 E E, Tree 10 E E] 3. after first iteration: processed = [Tree 4 (Tree 8 E E) (Tree 9 E E), Tree 5 (Tree 10 E E) E, Tree 6 E E, Tree 7 E E] after second iteration: processed = [Tree 2 (Tree 4 (Tree 8 E E) (Tree 9 E E)) (Tree 5 (Tree 10 E E) E), Tree 3 (Tree 6 E E) (Tree 7 E E)] after third iteration: processed = [Tree 1 ... (the final tree)] 4. return (Tree 1 ...) The algorithm simplifies a bit if we follow the convention that the processed list always ends in an infinite list of empty trees, can you see why? regards, Bertram