Tree Junction - joinTree

Question

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)

Also set the function joinTrees :: Btree a -> Ltree b -> Maybe (Ftree a b) that when the trees are compatible they are joined into one.

I resolved it this way : joinTree :: Btree a -> Ltree b -> Maybe (Ftree a b)

joinTree (Node x Empty Empty) (Fork (Tip a)(Tip b)) = Just (No x (Leaf a)(Leaf b))
joinTree (Node x l1 r1) (Fork l2 r2) | alturaB (Node x l1 r1) == ltHeight (Fork l2 r2) = (No x l r)
                                     | otherwise = Nothing

However, do not compile. Can find the error or know of a possible resolution: where l = joinTree l1 l2 r = joinTree r1 r2

Answer 1

There are some fallacies in the code, such as assuming that two trees of the same height are computable in:

alturaB (Node x l1 r1) == ltHeight (Fork l2 r2)

Such a statement is not always true.

Then record as a result (No x l r) Will be invalid, because according to the signing a value is expected Just _.

In order to solve this problem it is first necessary to consider in which cases a junction of the two types of trees is impossible:

• joinTrees Empty (Fork _ _) : Shall return Nothing, since when the Btree presents the value Empty this must correspond to a literal value Ltree, that is to say it must correspond to a value Tip _.
• joinTrees (Node _ _ _) (Tip _) : Shall return Nothing, for a reason analogous to the above mentioned. Are values not matching.

Now that we have the cases where the program have to fail, let us look at the case of failure:

• As in any other Tree the case of stopping should be at the ends, the ends of these our corresponding trees is as follows - joinTrees Empty (Tip a) - For this is the only possible case for the extremities, and at this point we must return a Just Leaf with the corresponding end value.

Then we want to create the function itself, to form this function we will need to obtain values corresponding to Nothing or extract beam values from fromJust, such a way that it will be necessary to import the library data.Maybe, and analyse successively for cases where it is obtained Nothing next tree or values Just.

Following a possible resolution:

import Data.Maybe

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)

joinTrees :: BTree a -> LTree b -> Maybe (FTree a b)
joinTrees Empty (Fork _ _)     = Nothing
joinTrees (Node _ _ _) (Tip _) = Nothing
joinTrees Empty (Tip a)        = Just $ Leaf a
joinTrees (Node a l1 r1) (Fork l2 r2) = 
                 if isNothing joinL || isNothing joinR
                  then Nothing
                 else Just $ No a exctL exctR
         where joinL = joinTrees l1 l2
               joinR = joinTrees r1 r2
               exctL = fromJust joinL
               exctR = fromJust joinR

Answer 2

I remember asking that question in one of my charts here’s the code:

joinTrees :: BTree a -> LTree b -> Maybe (FTree a b)
joinTrees (Empty) (Tip x) = Just (Leaf x)
joinTrees (Node r ae1 ad1) (Fork ae2 ad2) = Just (No r aux1 aux2)
                                            where Just aux1 = joinTrees ae1 ae2
                                                  Just aux2 = joinTrees ad1 ad2 
joinTrees _ _ = Nothing