Tree Transformation

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 splitFTree :: FTree a b -> (BTree a, LTree b) function that separates a tree with information on nodes and leaves in two type trees different.

    
asked by anonymous 02.12.2017 / 21:13

1 answer

1

To begin, you need to consider the following:

  • BTree - It is a tree in which the information is stored in the Nodes, but it is not stored in the ends, since these are of Empty type.
  • LTree - Is a tree whose information is stored only at its extremities.
  • FTree - It is a "full" tree, since it both stores its information in the Nodes and in its extremities.
  • Resolving this exercise will require the use of Tupling . First it is advisable to analyze what each argóre obtains in its extremities, and to do the Pattern Matching . It is then useful to go through the tree and record the information that corresponds 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
    
        
    03.12.2017 / 02:35