Jump to content
Xikilin

Fold: percorrer árvores

Recommended Posts

Xikilin

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

Share this post


Link to post
Share on other sites
Baderous

Estás a trocar a ordem dos argumentos. Null não corresponde a (b -> a -> a -> a), mas sim a Tree b, e o mesmo para o 2º ramo da definição.

Share this post


Link to post
Share on other sites
Xikilin

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?

Edited by Rui Carlos
GeSHi

Share this post


Link to post
Share on other sites
Xikilin

Será 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 f (Node n l r) = f n (foldt e f l)(foldt e f r)

Edited by Baderous
geshi

Share this post


Link to post
Share on other sites
Xikilin

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

Share this post


Link to post
Share on other sites
pdfrod

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.

Share this post


Link to post
Share on other sites
Xikilin

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?

Edited by Rui Carlos
GeSHi

Share this post


Link to post
Share on other sites
pdfrod

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

Share this post


Link to post
Share on other sites
Xikilin

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

Share this post


Link to post
Share on other sites
pdfrod

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

Share this post


Link to post
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

×
×
  • 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.