Linguagem de Programação 2/1A
Prova 2 -- 20/07/96

1) (1.5) 
Avalie a seguinte expressão utilizando innermost, 
outermost e graph reduction:

 average (map (+1) [8,10])

onde average xs = (sum xs) / (length xs)

2) 
data Btree a = Tip a | Bin (Btree a) (Btree a)

Dada uma árvore com números em suas folhas:

(1.0) faça uma função que retorne a mesma árvore, 
      mas com os nós que contém apenas folhas
      substituidos pela soma das folhas.

(1.0) utilize a função acima para definir uma função
      que retorne a soma de uma árvore.

(0.5) defina uma função ziptree que dada duas
      árvores com o mesmo formato retorne uma árvore de pares (cada
      elemento do par obtido de uma das árvores).

3) 
data Grafo a = No a [Grafo a]

Um grafo dirigido pode ser representado por uma lista de pares, onde cada um
dos elementos do par representa um vértice e cada par representa um
arco, i.e. [(1,2),(2,3),(2,4)] indica que o vértice 2 pode ser atingido a
partir do vértice 1 e os vértices 3 e 4 a partir do vértice 2.
Utilizando o tipo de dados Grafo definido acima, este mesmo grafo
pode ser representado por -No 1 [No 2 [No 3 [],No 4 []]]-
Defina funções utilizando o tipo Grafo para:

(1.0) dado um vértice a retorne a lista de todos os 
      vértices que podem ser atingidos diretamente a partir de a.
(1.0) dado um vértice a retorne a lista de todos os vértices 
      que podem ser alcançados a partir de a. 
      Assuma que o grafo é acíclico.
(1.0) converter um grafo descrito usando o tipo Grafo para
      a notação usando listas.
      Assuma que o grafo é acíclico.



4) 
(0.5) Defina uma função fliptree que dada uma árvore
      retorna a árvore invertida como em um espelho.
(1.0) Prove por indução a seguinte propriedade:

    fliptree (fliptree xs) = xs


5) (1.5)
Defina uma função que dada uma árvore retorne
uma árvore de pares onde o primeiro elemento é um número
sequencial do nó e o segundo o elemento original daquele nó.