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

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.2) 
Disponível em: 27/09/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) 
Luiz Henrique de Souza (lhs2@cin.ufpe.br) 
Renato Vieira Leite de Barros (rvlb@cin.ufpe.br) 
Roberto Costa Fernandes (rcf6@cin.ufpe.br) 
 
1. 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 
 
2. Qual a diferença entre avaliação estrita e avaliação preguiçosa (lazy evaluation)? 
Mostre exemplos desta diferença. 
 
3. Dado um tipo de dados que representa expressões aritméticas, que podem 
conter operações de soma, subtração, inteiros e variáveis (representada pelo tipo de 
dados Expr, abaixo), faça uma função chamada “avaliar” que, dado uma lista com o 
valor das variáveis e uma expressão, calcule o valor da 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 
 | Variavel String -- representa uma variável, como “x” ou “y” 
 
avaliar :: [(String, Int)] -> Expr -> Int 
 
Exemplo: 
-- expressão (x + (y - 33)) + (22 + x) 
expressao = Soma (Soma (Variavel “x”) (Subtrai (Variavel “y”) (Literal 33))) (Soma 
(Literal 22) (Variavel “x”)) 
 
-- (avaliar [(“x”, 10), (“y”, 20)] expressao) = 29 
 
 
 
 
 
 
 
 
 
 
Texto para as questões 4 e 5. 
ROT-13 é o nome que se costuma usar para um procedimento simples, mas eficaz 
para garantir que textos eletrônicos não sejam lidos por distração ou acidente. 
ROT-13 vem do inglês, ROTate by 13 places, “ROTacionar 13 posições”. 
 
ROT-13 é uma cifra de César aplicável apenas aos caracteres alfabéticos (da língua 
inglesa) e com passo 13. O algoritmo faz a troca conforme o exemplo abaixo: 
 
 
4 . 
a) Considerando uma chave para representar esta cifra como uma lista de pares 
informando que caracter deve substituir qual outro, implemente uma função cipher 
para realizar esta substituição em uma String, a partir de uma Chave, retornando 
uma String modificada como resultado. Qualquer caracter que não esteja na Chave 
deve aparecer inalterado na String de saída. 
 
type Chave = [(Char, Char)] 
 
rot13parcial :: Chave -- troca ‘a’ por ‘n’, ‘b’ por ‘o’, etc. 
rot13parcial = [(‘a’, ‘n’), (‘b’, ‘o’), (‘c’, ‘p’), (‘d’, ‘q’), (‘e’, ‘r’), (‘f’, ‘s’), 
 (‘g’, ‘t’), (‘h’, ‘u’), (‘i’, ‘v’), (‘j’, ‘w’), (‘k’, ‘x’), (‘l’, ‘y’), (‘m’, ‘z’)] 
 
--cipher :: Chave -> String -> String 
--Exemplo: cipher rot13parcial “hello*hello” = “uryyo*uryyo” 
 
b) Para decifrar o código, é preciso inverter a Chave. Faça uma função que inverta a 
ordem de cada um dos pares de uma Chave (lista de pares de caracteres): 
 
-- inverteChave :: Chave -> Chave 
--Exemplo: inverteChave rot13parcial = [(‘n’, ‘a’), (‘o’, ‘b’), (‘p’, ‘c’), ... 
c) Uma implementação diferente da função cipher poderia usar uma função no lugar 
dos pares de caracteres para representar a chave. Defina esta outra versão da 
função cipher, chamada cipherf. 
 
type FuncaoChave = (Char -> Char) 
 
trocaSoLetraL :: FuncaoChave 
trocaSoLetraL 'l' = 'b' 
trocaSoLetraL c = c 
 
--cipherf :: FuncaoChave -> String -> String 
--Exemplo: cipherf trocaSoLetraL “hello*hello” = “hebbo*hebbo” 
 
d) Usando uma expressão do tipo Chave (lista de pares), você conseguiria gerar 
uma função que pode ser usada como chave para a função cipherf? Em caso 
afirmativo, demonstre. Caso contrário, justifique. 
--chaveToFuncaoChave :: Chave -> FuncaoChave 
--Exemplo: cipherf (chaveToFuncaoChave rot13parcial) “hello*hello” = 
“uryyo*uryyo” 
 
5. Para uma maior eficiência no processo de busca dos caracteres em uma chave, 
podemos fazer a busca dos caracteres a serem trocados usando uma árvore binária 
em que cada nó, além da informação de uma letra e sua substituição, possua sub-
árvores para a busca de letras menores ou maiores que aquela letra. Se a letra não 
for achada na árvore, a substituição não ocorre. Escreva esta função cipherT, que 
usa uma árvore KeyTree definida abaixo. 
 
data KeyTree = Empty | Node Char Char KeyTree KeyTree 
 
chaveParcial :: KeyTree 
chaveParcial = Node ‘h’ ‘u’ (Node ‘c’ ‘p’ (Node ‘b’ ‘o’ (Node ‘a’ ‘n’ Empty Empty) 
Empty) (Node ‘e’ ‘r’ Empty Empty)) (Node ‘l’ ‘y’ Empty (Node ‘m’ ‘z’ Empty Empty)) 
 
--cipherT :: KeyTree -> String -> String 
--Exemplo: cipherT chaveParcial “hello*hello” = “uryyo*uryyo” 
 
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.