Linguagens de Programacao 2/1A
Prova 3 -- 25/11/96

1) 2.0
Avalie a seguinte expressao usando innermost, outermost e graph reduction:

double (head (repeat (2*2)))

2) 2.0
Prove por inducao a seguinte propriedade:

reverse (tips t) = tips (fliptree t)

se necessario use a seguinte propriedade:

reverse (xs ++ ys) = reverse ys ++ reverse xs


3) 3.0
Dado o tipo expressao booleana abaixo (com variaveis), 
defina uma funcao simpl
para simplificar uma expressao, usando as seguintes propriedades:

data BExp = T | F | And BExp BExp | Or BExp BExp | Not Bexp | Var Char

not True = False
not False = True
True  && x     = x             True  || x     = True
x     && True  = x             x     || True  = True
False && x     = False         x     || False = x
x     && False = False         False || x     = x

simpl :: BExp -> BExp

simpl (And (Var 'a') (Or F (Var 'x'))) = And (Var 'a') (Var 'x')

4) 3.0
Dado tipo BExp acima faca uma funcao de avaliacao
eval que avalie uma expressao booleana, recebendo tambem um
mapeamento entre variaveis e valores.

eval :: [(Char,Bool)] -> BExp -> Bool

eval [('y', True),('x',True)] (And (Var 'x') (And (Var 'y') T)) = True

Funcoes auxiliares:

repeat x = x : repeat x            tips (Tip a) = [a]
double x = x + x                   tips (Bin a b) = tips a ++ tips b

fliptree (Tip a) = Tip a
fliptree (Bin a b) = Bin (fliptree b) (fliptree a)

reverse [] = []
reverse (a:as) = reverse as ++ [a]