CODEWITHSUNDEEP
haskelltreefunctional-programming
fotg
fotg

Reputation: 639

Converting rose trees to different binary tree types

I am completely lost on how to do some tree conversions in Haskell. I need to go from a rose tree defined as: 

data Rose a = Node a [Rose a] deriving (Eq, Show, Ord)

to a binary tree which is defined as:

data Btree a = Empty | Fork a (Btree a) (Btree a) deriving (Eq, Show, Ord)

In my class I was given a function that is similar, but using a different definition of the binary tree. For that function the rose tree is defined the same and the binary tree is defined as:

Btree a = Leaf a | Fork (Btree a) (Btree a)

with the function from rose tree to binary tree defined as:

toB :: Rose a -> Btree a
toB (Node x xts) = foldl Fork (Leaf x) (map toB xts)
toB (Node x []) = foldl Fork (Leaf x) []

I have the answer but I don't know how to convert it so that it works with the new definition of Btree.

Upvotes: 1

Views: 1678

Answers (2)

sclv
sclv

Reputation: 38893

Try to write a function converting from the first to the second definition of the binary tree. Then convB . toB is your new function! Now, systematically create a new function that acts directly as a fusion of the two, by inlining one into the other, and you'll get a straightforward and elegant solution.

Upvotes: 1

Jack Kelly
Jack Kelly

Reputation: 18657

When I did something like this, I considered the "left" subtree to be the first child, and the "right" subtree to be the siblings of the node. This means that you convert the tree like so:

     h                 h
    /|\               /
   / | \             /
  b  d  e     ==>   b->d->e
 / \   / \         /     /
a   c f   g       a->c  f->g

h is still the root, but in the second diagram / is the left subtree and -> is the right. Leaves have no left subtree, but might have siblings (right subtrees). The root has no right subtree, but might have children (left subtree). Internal nodes have both.

Does that help?

Upvotes: 2

Related Questions