Jump to content

Fold: percorrer árvores


Xikilin
 Share

Recommended Posts

Boas Noites Pessoal,

Mais uma vez aqui estou a precisar de ajuda.

Preciso de criar uma função que implementa uma recursão sobre as sub-árvores esquerda e direita de um nó.

Criei o construtor:

data Tree v = Node v (Tree v) (Tree v) | Null

o tipo tem de ser:

foldt :: a -> (b -> a -> a -> a) -> Tree b -> a

1º parametro - valor retornado quando é folha

2º parametro - é uma função com 3 parametros (nó corrente, resultado chamada recursiva arvore esquerda, resultado chamada recursiva arvore direita)

3º parâmetro - arvore a processar

O tipo retornado corresponde ao tipo de retorno da função (segundo argumento).

Eu fiz assim:

data Tree v = Node v (Tree v) (Tree v) | Null
foldt :: a -> (b -> a -> a -> a) -> Tree b -> a
foldt e Null _ = e
foldt e (Node l n r) f = f n (foldt e l f) (foldt e r f)

erro:

ERROR "xxxxxxx.hs":386 - Type error in explicitly typed binding
*** Term           : Null
*** Type           : Tree c
*** Does not match : a -> b -> b -> b

Alguém me consegue ajudar????

Edited by thoga31
Tags code + GeSHi
Link to comment
Share on other sites

Alterei para isto:

data Tree v = Node v (Tree v) (Tree v) | Null
foldt :: a -> (b -> a -> a -> a) -> Tree b -> a
foldt e Null _ = e
foldt e (Node l n r) f = f n (foldt e l f) (foldt e r f)

alguma coisa está mal nas chamadas recursivas do foldt mas não estou a conseguir perceber a lógica.

Alguém consegue ajudar?

Link to comment
Share on other sites

Neste momento tenho isto:

-- 1)
data Tree v = Node v (Tree v) (Tree v) | Null
foldt :: a -> (b -> a -> a -> a) -> Tree b -> a
foldt lf _ Null = lf
foldt lf tr (Node cn l r) = tr cn (foldt lf tr l)(foldt lf tr r)

testTree = Node 5 (Node 3 (Node 1 Null Null) (Node 2 Null Null)) (Node 4 Null Null)

-- 2)

------weight---------
weight:: Num a => Tree b -> a
weight = foldt 0 (\ _ l r -> 1 + l + r)

-- ou --

weight2 :: Num a => Tree b -> a
weight2 (Null) = 0
weight2 (Node _ l r) = 1 + weight2 l + weight2 r


------depth---------
depth :: (Num a, Ord a) => Tree b -> a
depth = foldt 0 (\ _ l r -> 1 + max l r)

-- ou --

depth2 :: (Num a, Ord a) => Tree b -> a
depth2 (Null) = 0
depth2 (Node _ l r) = 1 + max (depth2 l) (depth2 r)

------toString---------
--toString :: Show a => Tree a -> [Char]

------sumt---------
sumt :: Num a => Tree a -> a
sumt = foldt 0 (\ cn l r -> cn + l + r)

-- ou --

sumt2 :: Num a => Tree a -> a
sumt2 Null = 0
sumt2 (Node cn Null Null) = cn
sumt2 (Node cn l r) = cn + sumt2 l + sumt2 r

preciso de criar uma função toString :: Show a => Tree a -> [Char] que retorna uma string que descreve a árvore usando parêntesis ex.: ((1)3(2))5(4) para representar a árvore Node 5 (Node 3 (Node 1 Null Null) (Node 2 Null Null)) (Node 4 Null Null).

Alguém me consegue dar umas dicas????

Não estou a ver como construir isto...

Edited by Baderous
geshi
Link to comment
Share on other sites

Como de costume, começa por enumerar os casos:

toString :: Show a => Tree a -> [Char]
toString Null = ...
toString (Node v l r) =...

No caso do Null, parece-me que o que faz sentido é retornar a string vazia. No caso de termos um Node, queremos algo do género "(string da árvore esquerda) valor do Node (string da árvore direita)". Se a string de uma sub-árvore for vazia, então não se coloca os parêntesis.

Link to comment
Share on other sites

Fiz assim:

toString :: Show a => Tree a -> [Char]
toString (Node cn Null Null) =  show cn
toString (Node cn l r) = "(" ++ toString l ++ ")" ++  show cn ++ "(" ++ toString r ++ ")"

Retorna aquilo que pede no enunciado.

Alguma sugestão de melhoria?

Já agora, como consigo construir isto apartir da função foldt:

foldt :: a -> (b -> a -> a -> a) -> Tree b -> a
foldt lf _ Null = lf
foldt lf tr (Node cn l r) = tr cn (foldt lf tr l)(foldt lf tr r)

????

Acho que o caso do Null não se aplica, apenas preciso de verificar no primeiro se é folha, caso seja, mostra-a.

Penso que não existem árvores vazias, posso é ter apenas o nó raiz que é folha. Estou certo?

Link to comment
Share on other sites

Bom eu não sei o enunciado do problema, portanto não sei se faz sentido assumir que não existem árvores vazias. Não tendo mais informação, não vejo motivo para impedir a seguinte invocação

toString Null

.

Para além disso a tua solução falha na seguinte situação:

toString (Node 1 Null (Node 2 Null Null))
Link to comment
Share on other sites

Deverá ser assim então:

toString :: Show a => Tree a -> [Char]
toString Null = ""
toString (Node cn Null Null) =  show cn
toString (Node cn l Null) =  "(" ++ toString l ++ ")" ++  show cn
toString (Node cn Null r) = show cn ++ "(" ++ toString r ++ ")"
toString (Node cn l r) = "(" ++ toString l ++ ")" ++  show cn ++ "(" ++ toString r ++ ")"
Edited by thoga31
Tags code + GeSHi
Link to comment
Share on other sites

Funciona, mas na minha opinião não é muito elegante pois há demasiada repetição. Prefiro a seguinte solução:

toString :: Show a => Tree a -> [Char]
toString Null = []
toString (Node v l r) = (paren $ toString l) ++ show v ++ (paren $ toString r)
 where
   paren [] = []
   paren s = "(" ++ s ++ ")"
Edited by Kimio
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.