Paradigmas de Linguagens de Programação - Lista 2 2016 1

Prévia do material em texto

2ª Lista de Paradigmas de Linguagens Computacionais 
Lista de Exercícios de Revisão do Paradigma Funcional 
 
CIn – UFPE (2016.1) 
Disponível em: 28/04/2016 
 
Professores: 
André Luís de Medeiros Santos (alms@cin.ufpe.br) 
Henrique Emanuel Mostaert Rebêlo (hemr@cin.ufpe.br) 
 
Monitores: 
Álvaro Arthur Canto Sabino de Miranda Costa (aacsmc@cin.ufpe.br) 
Gustavo de Oliveira Feitosa (gof@cin.ufpe.br) 
Ihago Henrique Lucena e Silva (ihls@cin.ufpe.br) 
 
1. Qual a diferença entre avaliação estrita e avaliação preguiçosa (lazy evaluation)? 
Mostre exemplos desta diferença. 
 
2. Apresente a inferência dos tipos das seguintes expressões (função f e função g), 
e dê um exemplo de uso das mesmas com parâmetro(s)/argumento(s) e um 
resultado. 
 
f :: 
f = map (+) 
 
g :: 
g = (.) map map 
 
Para ajudar a resolver a questão, abaixo estão os tipos de map, (.) e (+): 
map :: (a -> b) -> [a] -> [b] 
( . ) :: (b -> c) -> (a -> b) -> (a -> c) 
( + ) :: Int -> Int -> Int 
 
 
3. Um sorteio de Mega-Sena pode ser representado por uma lista de seis números. 
Um conjunto de cartões de apostas pode ser representado por uma lista de listas 
(cada lista representando um cartão). Assuma que os números do resultado 
premiado/sorteado e os números em cada cartão estão ordenados. 
 
type Resultado = [Int] 
type Jogos = [[Int]] 
 
Defina funções para: 
a) a função premiados retorna o números de cartões premiados com a sena. 
premiados :: Resultado -> Jogos -> Int 
 
b) a função acertos retorna a lista com o número de acertos em cada cartão (do 
primeiro cartão, do segundo, do terceiro, etc.). 
acertos :: Resultado -> Jogos -> [Int] 
 
c) a função numPremios retorna uma tupla de três inteiros contendo a quantidade 
de cartões premiados com 4, 5 ou 6 acertos, respectivamente. 
numPremios :: Resultado -> Jogos -> (Int, Int, Int) 
 
4. Uma linguagem de programação baseada em pilha possui apenas uma pilha 
(stack) onde ficam os dados/operandos e todas as instruções são apenas de 
empilhar, desempilhar ou fazer operações consumindo (lendo) os dados no topo da 
pilha e deixando o resultado final o topo da pilha. 
Dados os tipos de dados abaixo e os exemplos, escreva um interpretador que 
executa as instruções com o comportamento abaixo: 
 
data Instrucao = 
 PUSH Int -- empilha um valor inteiro 
 | POP -- desempilha (remove) um valor do topo da pilha 
 | ADD -- remove (lê) os dois valores no topo da pilha e deixa a soma deles 
no topo da pilha 
 | SUB -- remove (lê) os dois valores no topo da pilha e deixa a diferença do 
primeiro menos o segundo no topo da pilha 
 | DUP -- repete o mesmo valor no topo da pilha (duplica ele) 
 
 
 
type Pilha = [Int] 
 
a) evalI avalia uma única instrução em uma dada pilha. 
evalI :: Instrucao -> Pilha -> Pilha 
 
Exemplos: 
--evalI ADD [1, 2, 3, 4, 5] = [3, 3, 4, 5] (soma 1+2) 
--evalI DUP [5, 1] = [5, 5, 1] (repete/copia o valor no topo da pilha) 
--evalI SUB [1, 2, 3, 4] = [-1, 3, 4] (calcula 1-2) 
--evalI (PUSH 7) [1, 2, 3] = [7, 1, 2, 3] (insere o 7 no topo) 
--evalI POP [8, 2, 3] = [2, 3] (remove o 8) 
 
b) evalProg avalia um programa (sequência de instruções) a partir de uma pilha 
inicial vazia e retorna o estado final da pilha depois da avaliação. 
evalProg :: [Instrucao] -> Pilha 
 
Exemplo: 
--evalProg [PUSH 3, PUSH 5, DUP, ADD, SUB] = [7] (5+5-3) 
 
5. Faça uma função translate que traduz expressões (tipo Expr, abaixo) para uma 
sequência (lista) de instruções que, se usadas com o avaliador da questão 8, avaliam 
a expressão. 
 
data Expr = Literal Int -- um número 
 | Soma Expr Expr -- soma as duas expressões 
 | Subtrai Expr Expr -- subtrai a segunda expressão da primeira 
 | Dobra Expr -- dobra o valor da expressão 
 
translate :: Expr -> [Instrucao] 
 
Exemplo: 
translate (Soma (Literal 5) (Dobra (Subtrai (Literal 4) (Literal 1)))) = [PUSH 1, 
PUSH 4, SUB, DUP, ADD, PUSH 5, ADD] 
 
 
 
 
Texto para as questões de 6 a 10. 
Dado um tabuleiro de Jogo de Damas representado pelos seguintes tipos de dados: 
 
data Peca = P | B | V deriving (Eq, Show) 
type Tabuleiro = [[Peca]] 
 
Onde P representa uma peça preta, B uma peça branca e V uma casa vazia. O 
primeiro elemento da primeira lista é o elemento (0, 0) e a primeira peça preta está 
na posição (0, 0) (linha 0, coluna 0). Sabendo que um tabuleiro tem tamanho 8 x 8 
e que as peças se movem na diagonal para espaços vazios (desconsidere a captura 
de peças), defina as seguintes funções: 
 
tabuleiroInicial :: Tabuleiro 
tabuleiroInicial = [[P, V, P, V, P, V, P, V], 
 [V, P, V, P, V, P, V, P], 
 [P, V, P, V, P, V, P, V], 
 [V, V, V, V, V, V, V, V], 
 [V, V, V, V, V, V, V, V], 
 [V, B, V, B, V, B, V, B], 
 [B, V, B, V, B, V, B, V], 
 [V, B, V, B, V, B, V, B]] 
 
 
 
 
 
6. count :: Tabuleiro -> (Int, Int), que conta quantas peças brancas e quantas peças 
pretas estão no tabuleiro. 
 
7. tabuleiroValido :: Tabuleiro -> Bool, que verifica se o tabuleiro tem tamanho 
8 x 8 e se as peças existentes estão em casas válidas, sempre na diagonal. 
Exemplo: 
--tabuleiroValido tabuleiroInicial = True 
 
8. promoveDama :: Tabuleiro -> Bool, que verifica se tem alguma peça branca na 
primeira linha ou se tem alguma peça preta na última linha, ou seja, se existe alguma 
peça no tabuleiro que poderia ser promovida a dama. 
Exemplo: 
--promoveDama tabuleiroInicial = False 
 
9. verificaJogada :: (Int, Int) -> (Int, Int) -> Tabuleiro -> Bool, que verifica se uma 
jogada é possível/válida, ou seja, se é uma jogada de uma casa que tem uma peça 
para outra vazia na diagonal. 
Exemplos: 
--verificaJogada (2, 0) (3, 1) tabuleiroInicial = True 
--verificaJogada (2, 0) (3, 2) tabuleiroInicial = False 
--verificaJogada (2, 0) (3, 3) tabuleiroInicial = False 
 
10. move :: (Int, Int) -> (Int, Int) -> Tabuleiro -> Tabuleiro, que move uma peça de 
uma casa para outra, contando as linhas e colunas a partir do primeiro elemento da 
primeira lista sendo o elemento (0, 0). Essa função recebe a casa inicial, a casa 
final, o tabuleiro inicial e retorna um novo tabuleiro modificado.