• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Baderous

Árvore e fold

10 mensagens neste tópico

Tenho a seguinte estrutura de dados, que representa uma árvore com um número arbitrário de descendentes por nodo:

data Arvore t = Vazias | Arvs t [(Arvore t)]

E tenho uma função mapArv que aplica uma função a todos os elementos de uma árvore:

mapArv :: (a -> b) -> (Arvore a) -> (Arvore b)
mapArv _ Vazias = Vazias
mapArv f (Arvs r l) = Arvs (f r) (map (mapArv f) l)

Agora quero definir esta mesma função usando um fold para árvores que já é dado:

foldArv :: (b -> [b] -> b) -> b -> Arvore a -> b
foldArv f e Vazias = e
foldArv f e (Arvs r l) = let l' = map (foldArv f e) l
		 in f e l'

O problema é que não estou a conseguir definir a função que devo usar no fold, porque também não percebo muito bem como é que uso uma função de a -> b dentro da definição do foldArv (b -> [ b] -> b).

O que tenho é isto, mas não está bem, nem concorda com o tipo da função:

--mapArv' :: (a -> b) -> (Arvore a) -> (Arvore b)
mapArv' f a = foldArv (\x y -> (f x) y) Vazias a

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Posso estar a ver mal, mas com a definição que tens de foldArv diria que é impossível implementares o mapArv' (presumindo que deverá ter a mesma funcionalidade que o mapArv). Porque estás a perder o valor de 'r' na definição de foldArv.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois, mas é assim que aparece no livro que estou a ler. :|

Se calhar está errado.

No entanto ela funciona para os seguintes exemplos:

contanodos' a = foldArv f 0 a
where f r l = 1 + sum l

peso' a = foldArv f 0 a
where f r [] = 1
      f r (x:xs) = 1 + maximum (x:xs)

Estranho...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

foldArv f e Vazias = e
foldArv f e (Arvs r l) = let l' = map (foldArv f e) l
                         in f r l'
                         
map2 f t = foldArv (\x l -> Arvs (f x) l) Vazias t

Tive que alterar a definição do foldArv.

Concordo com o Betovsky, a anterior definição não fazia qualquer sentido.

O e é o valor que devolves no caso de paragem. A função é aplicada sobre valor actual e o resultado de a aplicares recursivamente sobre os descendentes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ah agora já faz mais sentido. Eu já tinha chegado a essa definição do map, mesmo tendo o foldArv incorrecto, mas como não concordava com os tipos, dava-me erro. Thanks! :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aproveito esta thread sobre árvores para fazer uma pergunta. Tenho um exercício onde me pede para fazer uma função que faça a travessia de uma árvore binária, de tal modo que verifique o seguinte:

data ArvBin x = Empty | Nodo x (ArvBin x) (ArvBin x)

trav :: ArvBin a -> [a]

-- reconstroi (trav a) = a

reconstroi = foldl acrescenta Empty

A função acrescenta não está definida. Do que eu percebi, tenho de fazer uma travessia por níveis da árvore (pela lógica do foldl, parece-me ser isso). O problema é que não estou a ver como o vou fazer. Já pensei em fazer algo do género: da travessia resultava uma lista de listas, em que cada lista elemento tinha os nodos de cada nível da árvore. Mas não sei como fazer isso. Alguém me dá ideias?

EDIT: O melhor que consegui fazer foi isto:

trav :: ArvBin a -> [a]
trav Empty = []
trav (Nodo x e d) = case e of 
	  Empty -> case d of
		   Empty -> []
		   (Nodo n _ _) -> [n] ++ trav d
	  (Nodo r _ _) -> case d of
			  Empty -> [r] ++ trav e
			  (Nodo v _ _) -> [x]++[r]++[v]++(trav e)++(trav d)

Mas o problema é que ele faz primeiro a travessia para a sub-árvore esquerda e só depois para a direita. Assim, o único sítio onde a travessia é feita correctamente é logo na 1ª iteração.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, eu diria que só funciona se a tua árvore for ordenada. Nessa caso só tens de percorrer a árvore em inorder.

Ficavas com algo do género:

trav Empty = []
trav (Nodo x e d) = x : trav e ++ trav d

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Então é fazer uma travessia inorder? E aquela função "acrescenta" então como é que insere os nodos na árvore vazia?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Inseres normalmente numa arvore ordenada, sem balancear a mesma.

acrescenta Empty v = Nodo v Empty Empty
acrescenta (Nodo x e d) v | x > v = Nodo (acrescenta e v) d
                          | otherwise = Nodo e (acrescenta d v)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Oh pois é, eu estava a pensar que a árvore só podia ser construída por níveis, por isso é que estava a fazer estes filmes todos...:D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora