Transformation of Trees

Question

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.

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