2
\$\begingroup\$

I was trying to implement a foldTree function to generate a balanced binary tree from a list of values using foldr (Question 2 here), but the resulting solution is not really written in a proper manner:

data Tree a = Leaf
            | Node Int (Tree a) a (Tree a)
            deriving (Show,Eq)


foldTree::[a]-> Tree a
foldTree a=_foldTree a 0 ((getHeight (length a))-1) (length a)
           where 
           _foldTree::[a]->Int->Int->Int->Tree a
           _foldTree a n h l
                        | n>=l = Leaf
                        | otherwise = Node h (_foldTree a (2*n+1) (h-1) l ) (a!!n) (_foldTree a (2*n+2) (h-1) l)


getHeight::Int->Int
getHeight n=ceiling(log (fromIntegral(n))/log 2)

The solution suffers from precision problems. And I think I can use some high level abstractions which I have been missing.

I am just making the heap (sort of, without ordering) out of the list.

\$\endgroup\$
2
\$\begingroup\$

While the output should be a balanced tree, it seems it's not required to be ordered in any way (at least the given example there isn't). So it's definitely not a heap. And the solution is required to use foldr, which yours doesn't satisfy.

You need to split the task into two parts:

  1. Inserting a new element into a balanced tree so that the result is again a balanced tree. The signature of the function should look somewhat like

    insert :: a -> Tree a -> Tree a
    

    If you're not sure how to implement insert, hover over the following box with another hint (but I'd strongly suggest you to try without it first):

    Inserting into an empty tree is trivial. If the tree is nonempty, check both subtrees and recursively insert the element into the subtree with less height. (If the heights are the same, just pick whichever is more convenient.) Since inserting an element this way keeps the height of a tree or increases it just by 1, the resulting tree is also balanced.

  2. Folding over the list using the insertion function. This part is easy, when you have 1.

\$\endgroup\$
  • \$\begingroup\$ My main problem is assigning and changing heights. How can I do so in single traversal. As you can see I am currently pre-calculating the heights and then assigning. \$\endgroup\$ – user2179293 Jun 29 '14 at 22:33
  • \$\begingroup\$ @user2179293 Don't think of the heights as something separate from nodes. The height is something that belongs to a node. I'd suggest you to implement two functions, AKA smart constructors, with signatures leaf :: Tree a (this will be just Leaf) and node :: Tree a -> a -> Tree a -> Tree a. Having them, you can create and manipulate trees without caring about the heights at all - node will compute the correct height automatically behind the scenes. \$\endgroup\$ – Petr Pudlák Jun 30 '14 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.