Jump to content
Baderous

Árvore e fold

Recommended Posts

Baderous

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

Share this post


Link to post
Share on other sites
Betovsky

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.


"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Share this post


Link to post
Share on other sites
Baderous

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

Share this post


Link to post
Share on other sites
Rui Carlos

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.

Share this post


Link to post
Share on other sites
Baderous

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! :(

Share this post


Link to post
Share on other sites
Baderous

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.

Share this post


Link to post
Share on other sites
Betovsky

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


"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Share this post


Link to post
Share on other sites
Baderous

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

Share this post


Link to post
Share on other sites
Betovsky

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)


"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Share this post


Link to post
Share on other sites
Baderous

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

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.