Transformation of Trees

Asked

Viewed 52 times

0

Considering the structures:

data BTree a = Empty | Node a (BTree a) (BTree a)
data LTree a = Tip a | Fork (LTree a) (LTree a)
data FTree a b = Leaf b | No a (FTree a b) (FTree a b)

Set the function splitFTree :: FTree a b -> (BTree a, LTree b) separating a tree with information on nodes and leaves on two type trees different.

haskell

1 answer

1


To begin with, the following must be taken into account::

  1. Btree - It is a tree in which the information is stored in the Nodes, but is not stored in the ends, since these are of the type Empty.
  2. Ltree - It is a tree whose information is stored only at its ends.
  3. Ftree - It is a "full" tree, as it both stores its information in the Nodes and at its ends.

The resolution of this exercise will require the use of Tupling. First it is recommended to analyze what each arvóre obtains in its extremities, and to make the respective Pattern Matching. Next it is useful to go through the tree and record the information that is equivalent to each tree.

Possible Resolution:

splitFTree :: FTree a b -> (BTree a, LTree b)
splitFTree (Leaf b)   = (Empty,Tip b)
splitFTree (No a l r) = (Node a b1 b2, Fork l1 l2)
      where (b1,l1) = splitFTree l
            (b2,l2) = splitFTree r

  • Thank you, that’s exactly what I intended :)

Browser other questions tagged haskell

You are not signed in. Login or sign up in order to post.