Junction of trees - joinTree

Question

Junction of trees - joinTree

Navigation

#1 by (1 votes)

0

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 joinTrees :: BTree function to - > LTree b - > Maybe (FTree a b) that whenever the trees are compatible they join them in one.

I solved 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, it does not compile. They can find the error or know of a possible resolution: where l = joinTree l1 l2 r = joinTree r1 r2

haskell

asked by anonymous 03.12.2017 / 18:05

1 answer

Force the user to enter enter Comparison of hashes in PHP

score 1 · Answer 1

There are some fallacies in the code, such as assuming 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.

Next, register as a result (No x l r) will be invalid , because signature expects Just strong>.

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

joinTrees Empty (Fork _ _) : You should return Nothing , since when BTree value Empty This should match a literal LTree literal value, in> Tip _ .
joinTrees (Node _ _ _) (Tip _) : You should return Nothing , for a similar reason as above. These are not matched values.

Now that we have cases where the program has to fail, let's look at the stopping case:

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

Then we want to create the function itself, to form this function we need to get values corresponding to Nothing you need to import Library Data.Maybe , and parse successively in cases where Nothing is obtained on the next tree or values Just .

A possible resolution follows:

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