Baixe o app para aproveitar ainda mais
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.
Compartilhar