Linguagens de Programação 2/1A
Prova 1 -- segunda chamada -- 28/06/96

1) (2.5) 
Faça a inferência de tipos das seguintes funções e expressões:

 (1.0) f a b c = b a (f a b (tail c))
 (0.5) foldr map
 (1.0) map (map fst)


2) 
Dada uma lista de inteiros, por exemplo

[1,3,7,2,1,8,9,15,22,6,55,77,22,33,21,12,1,23], defina uma função que:

(1.0) some cada dois elementos da lista, i.e. retorne
      [1+3,3+7,7+2,...] se tiver a lista acima como entrada.

(1.5) encontre a maior (mais longa) sequência crescente.
      No exemplo acima a maior (mais longa) sequência crescente é [1,8,9,15,22].
      Se houver mais de uma do mesmo tamanho retorne a primeira que encontrar.


3) 
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.
Defina funções para:

(0.5) dado um vértice a retorne a lista de todos os 
      vértices que podem ser atingidos diretamente a partir de a.

(1.5) 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.5) resolva o mesmo problema do item anterior, assumindo que
      o grafo pode ser cíclico.


4) (1.5)
Prove por indução a seguinte propriedade:
     filter even (map (+1) xs) = map (+1) (filter odd xs)


5) (1.0)
Um polinomio pode ser representado como uma lista de pares,
por exemplo o polin^omio 10x^14 + 2x^8 + x^7 + 3x^2 pode representado
pela lista [(10,14),(2,8),(1,7),(3,2)].
Defina uma função que some dois polin^omios, i.e.
(10x^14 + 2x^8 + x^7 + 3x^2) + (2x^12 + 2x^8 + 3x^7 + x) =
           10x^14 + 2x^12 + 4x^8 + 4x^7 + 3x^2 + x
Assuma que os expoentes estão em ordem decrescente.
 

6) (1.5)
Defina uma função que dada duas strings verifica 
se a primeira faz parte da segunda, i.e. 
f "badab" "ababadaba" = True