2
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)

Defina ainda a função joinTrees :: BTree a -> LTree b -> Maybe (FTree a b) que sempre que as árvores sejam compatı́veis as junta numa só.

Eu resolvi desta forma : 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

No entanto, não compila. Conseguem encontrar o erro ou sabem de uma possivel resolução: where l = joinTree l1 l2 r = joinTree r1 r2

2 Respostas 2

3

Há algumas falácias no código, como por exemplo assumir que duas árvores com a mesma altura são compátiveis em:

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

Tal afirmação nem sempre é verdade.

Seguidamente, registar como resultado (No x l r) Será inválido, pois segundo a assinatura é esperado um valor Just _.

Para a resolução deste problema é necessário primeiro termos em conta em que casos é que uma junção dos dois tipos de árvores é impóssivel:

  • joinTrees Empty (Fork _ _) : Deverá retornar Nothing, visto que quando a BTree apresenta o valor Empty este deve corresponder a um valor literal LTree, ou seja deverá corresponder a um valor Tip _.
  • joinTrees (Node _ _ _) (Tip _) : Deverá retornar Nothing, por uma razão análoga à de acima referida. São valores não correspondentes.

Agora que temos os casos em que o programa têm de falhar, analisemos o caso de paragem:

  • Como em qualquer outra Tree o caso de paragem deve ser nas extremidades, as extremidades destas nossas árvores correspondentes é a seguinte - joinTrees Empty (Tip a) - Pois este é o único caso possível para as extremidades, e neste ponto devemos retornar uma Just Leaf com o correspondente valor da extremidade.

De seguida queremos criar a função em si, para formar esta função será necessário obter valores correspondentes a Nothing ou extrair valores àtraves de fromJust, tal modo que será necessário fazer import da library Data.Maybe, e analisar sucessivamente para casos em que é obtido Nothing na àrvore seguinte ou valores Just.

Segue uma possível resolução:

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
1
  • Muito Obrigado, bastante exclarecedor :) 4/12/2017 às 22:20
1

Eu lembro me de ter feito essa pergunta numa das minhas fichas aqui está o código:

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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .