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

Prévia do material em texto

1ª Lista de Paradigmas de Linguagens Computacionais 
Lista de Exercícios do Paradigma Funcional 
 
CIn – UFPE (2016.2) 
Disponível em: 30/08/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. Sobre o paradigma funcional, desenvolva os seguintes conceitos: 
a) Transparência referencial 
b) Funções de alta ordem 
c) Currying 
d) Lambda Cálculo 
 
2. Implemente uma função que, dado 3 números inteiros, retorne um booleano 
indicando se pelo menos dois deles são números ímpares. 
 
3. Defina a função logic :: (Bool, Bool) -> (Bool, Bool, Bool) que tem como 
finalidade testar a tupla de entrada para cada um dos operadores lógicos 
(and, or, xor) e gerar uma tupla na qual seus membros são a resposta de cada teste. 
 
 
 
 
Exemplos: 
Main> logic (True, True) 
(True, True, False) 
 
Main> logic (False, True) 
(False, True, True) 
 
4. Crie uma função: triangulo :: (Int, Int, Int) -> (String, Int), que, dado 3 inteiros, 
verifique se os mesmos podem ser os lados de um triângulo. Se for possível forma-
lo retorne uma dupla com o tipo do triângulo formado (com relação às arestas) e o 
perímetro do mesmo, caso contrário imprima: (“Impossivel”, 0). 
 
Exemplos: 
Main> triangulo (7, 7, 11) 
(“Isosceles”, 25) 
 
Main> triangulo (7, 7, 7) 
(“Equilatero”, 21) 
 
Main> triangulo (7, 7, 15) 
(“Impossivel”, 0) 
 
5. 
a) Defina o tipo Ponto como sinônimo de uma tupla com três Float. Defina, 
também, a função distancia :: Ponto -> Ponto -> Float, que calcula a distância entre 
três pontos em um espaço tridimensional. 
 
Exemplo: 
Main> distancia (0, 0, 0) (1, 1, 1) 
1.7320508 
 
b) Agora defina o tipo Esfera como sinônimo de um Ponto central e um Float como 
raio. Defina, ainda, a função estaContido :: Esfera -> Ponto -> Bool, que diz se um 
ponto dado está contido ou não na superfície de uma esfera. 
 
 
 
Exemplos: 
Main> estaContido ((0, 0, 0), 1) (1, 1, 1) 
False 
 
Main> estaContido ((0, 0, 0), 1) (0, 0, 1) 
True 
 
6. Dado o limite inferior e o superior de um intervalo e o seu incremento, 
implemente, sem a utilização de listas, a função somaIntervalo :: Int -> Int -> Int -> 
Int que indique a soma dos números que pertencem a este intervalo. 
 
Exemplos: 
Main> somaIntervalo 1 7 2 
16 
 
Main> somaIntervalo 10 26 3 
105 
 
7. Implemente a função sumDigits :: Int -> Int cuja finalidade seja somar todos os 
dígitos de um número natural. 
 
Exemplos: 
Main> sumDigits 9182 
20 
 
Main> sumDigits 1002 
3 
 
8. Implemente a função: nPrimo :: Int -> Int, que encontre o N-ésimo número 
primo natural. A função deverá ser implementada de forma recursiva e sem a 
utilização de listas. 
 
Exemplos: 
Main> nPrimo 1 
2 
 
Main> nPrimo 2 
3 
 
Main> nPrimo 5 
11 
 
Main> nPrimo 750 
5693 
 
9. Devido à intensa quantidade de posts de política no Facebook, durante o período 
das eleições 2014, você decidiu que não gostaria de ver qualquer post que falasse 
de Dilma ou Aécio. Para isso você vai criar uma função limpaTimeline :: [String] -> 
[String] que recebe uma lista de posts e não mostra os que citam a palavra “Dilma” 
e/ou “Aecio”. 
 
Dica: 
Importe a biblioteca Data.List e utilize a função isInfixOf. Para importar a 
biblioteca, escreva no começo do arquivo o seguinte trecho de código: 
import Data.List 
 
A função isInfixOf :: Eq a => [a] -> [a] -> Bool pega duas listas e retorna True se a 
primeira lista está completamente contida em qualquer lugar da segunda lista. 
 
Exemplos: 
Main> limpaTimeline [(“Maria: Votarei em Dilma”), (“Pedro: Eu voto em Aecio”), 
(“Carolina: Hoje eh dia de votar”)] 
 
[("Carolina: Hoje eh dia de votar")] 
 
Main> limpaTimeline [(“Jose: Oi, eu sou o Goku!”), (“Melissa: Dilma x Aecio = Vou 
votar em branco”), (“Luigi: #partiu Votar”)] 
 
[(“Jose: Oi, eu sou o Goku!”), (“Luigi: #partiu Votar”)] 
 
10. Implemente em Haskell o algoritmo de ordenação Mergesort para ordenar uma 
lista de números inteiros. 
 
11. Combinação é um subconjunto com p elementos de um conjunto 
possivelmente maior com n elementos, onde p <= n. A combinação dos elementos 
[1, 2, 3], por exemplo, pode gerar os seguintes agrupamentos: [], [1], [2], [3], 
[1, 2], [1, 3], [2, 3] e [1, 2, 3]. Repare que a ordem dos elementos em cada 
agrupamento é irrelevante, logo mudar a ordem dos elementos não gera 
combinações diferentes. 
 
Crie uma função combinacoes :: [Int] -> [[Int]] para gerar todas as possíveis 
combinações sem repetição dos inteiros de um grupo de entrada. 
 
Exemplos: 
Main> combinacoes [81, 25] 
[[], [81], [25], [81, 25]] 
 
Main> combinacoes [1, 2, 3] 
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 
 
Main> combinacoes [10, -80, 14, 16] 
[[], [10], [-80], [10, -80], [14], [10, 14], [-80, 14], [10, -80, 14], [16], [10, 16], 
[-80, 16], [10, -80, 16], [14, 16], [10, 14, 16], [-80, 14, 16], [10, -80, 14, 16]] 
 
12. Escreva uma função: reduz1 :: [Int] -> [Int], que receba uma lista ordenada e 
para cada número que apareça n vezes, deverá aparecer (n-1) vezes na lista 
retornada. Utilize obrigatoriamente compreensão de listas (Ou seja, sem utilizar 
recursão) para implementar reduz1. 
 
Exemplo: 
Main> reduz1 [1, 1, 2, 2, 2, 2, 5, 9] 
[1, 2, 2, 2] 
 
13. O professor Carvalho precisa de uma função para catalogar todos os 
pokemons que ele encontrou até agora e saber quais faltam para sua coleção. 
Utilizando compreensão de listas, crie uma função catalogoPokemon :: Int -> Int -> 
[String] que recebe o intervalo do número dos pokemons que serão catalogados e 
constrói uma lista com todos os pokemons encontrados e desconhecidos naquele 
intervalo. 
 
O banco de dados do professor Carvalho é dado abaixo. 
 
pokemon :: Int -> String 
pokemon 1 = “Bulbasaur” 
pokemon 2 = “Ivysaur” 
pokemon 3 = “Venusaur” 
pokemon 4 = “Charmander” 
pokemon 5 = “Charmeleon” 
pokemon 6 = “Charizard” 
pokemon 7 = “Squirtle” 
pokemon 8 = “Wartortle” 
pokemon 9 = “Blastoise” 
pokemon 12 = “Butterfree” 
pokemon _ = “Unknown” 
 
Exemplos: 
Main> catalogoPokemon 1 9 
[“Bulbasaur”, “Ivysaur”, “Venusaur”, “Charmander”, “Charmeleon”, “Charizard”, 
“Squirtle”, “Wartortle”, “Blastoise”] 
 
Main> catalogoPokemon 7 12 
[“Squirtle”, “Wartortle”, “Blastoise”, “Unknown”, “Unknown”, “Butterfree”] 
 
14. Implemente uma função capaz de, dado um par de funções, executar um “fold 
matricial” comprimindo os elementos de uma determinada linha usando uma das 
funções e os resultados usando a outra. 
 
Exemplos: 
Main> foldMatrix (*) (+) [[1, 2, 3], [1, 2, 3]] 
12 
 
Main> foldMatrix (+) (*) [[1, 2, 3], [1, 2, 3]] 
36 
 
15. Crie a função (>.>) :: (a -> b) -> (b -> d) -> (a -> d) que receba 2 funções e 
retorne uma terceira função que é a aplicação sucessiva delas. 
 
Main> ((div 2) >.> (2*)) 2 
2 
 
Main> ((2*) >.> (div 2)) 2 
0 
 
16. Implemente a função multiFilter :: [(a -> Bool)] -> [a] -> [a], uma versão da 
função filter que recebe uma lista de funções e uma lista de um tipo qualquer, e 
retorna uma lista com os elementos filtrados por todas as funções da lista de 
funções.Exemplos: 
Main> multiFilter [even, (\x -> (mod x 5)==0)] [1..100] 
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100] 
 
Main> multiFilter [] “Janeiro” 
“Janeiro” 
 
17. Defina uma função g ::[Int] -> Bool que verifica que todo elemento de uma 
lista que está entre 0 e 100 (inclusive) é par. Utilize as funções map, filter e foldr. 
 
Exemplos: 
Main> g [0, 26, 153, 72, 68, 8] 
True 
 
Main> g [1, 12, 153, 73, 9] 
False 
 
Main> g [ ] 
True 
 
Main> g [1, 255] 
False 
 
 
 
18. Implemente a função: divs :: [Int] -> Int -> Int -> (Bool, Bool), que dada uma 
lista de inteiros, devolva uma tupla onde o primeiro membro indica se todos os 
números pares da lista são divisíveis pelo segundo argumento e o segundo membro 
indica se todos os números ímpares da lista são divisíveis pelo terceiro argumento. 
Para implementar a função divs, utilize obrigatoriamente as funções map, filter e 
alguma função fold (foldr, foldl, foldr1 ou foldl1). 
 
Exemplo: 
Main> divs [5, 6, 18, 35, 48, 57] 3 5 
(True, False) 
 
19. Determine o tipo das funções abaixo mostrando os passos até obter o 
resultado. Caso não seja possível determinar o tipo, explique o porquê. 
a) (.) map filter 
b) (.).map 
c) (.).(.) 
 
20. Para as funções g e h abaixo, verifique se elas estão corretas. Em caso 
afirmativo indique seu tipo. Caso contrário, explique qual o erro encontrado. 
 
a) g = map ff 
b) h = foldr ff 
 
Dados: 
ff :: (a -> [b]) -> Maybe a -> [b] 
ff f (Nothing) = [] 
ff f (Just x) = f x 
 
map :: (a -> b) -> [a] -> [b] 
foldr :: (a -> b -> b) -> b -> [a] -> b 
 
21. Para as expressões abaixo, indique se elas estão corretas. Em caso afirmativo 
indique seu tipo e seu resultado. 
 
 
a) map (even) (filter (>100) [10, 45, 300, 312, 561, 40, 28, 3]) 
b) snd (head (zip [1, 2, 3, 7] [True, True, False])) 
c) map (foldl1 (*)) [[0, 1], [1, 2, 4], [10]] 
 
22. Dada a expressão square (7 + 8), onde a função square está definida abaixo 
junto com as funções loop, nlist e dlist, há duas sequências de redução possíveis 
para esta expressão. 
 
square = \a -> a * a 
loop = \x -> x + loop x 
nlist = \n -> take n [n, 2*n..] 
dlist = \a -> \b -> map (\h -> div h (h-a)) [a..b] 
 
A primeira delas é a seguinte: 
 square (7 + 8) 
 = square 15 --definição do operador (+) 
 = 15 * 15 --definição da função square 
 = 225 --definição do operador (*) 
 
A segunda sequência de redução para a mesma expressão é: 
 square (7 + 8) 
 = (7 + 8) * (7 + 8) --definição da função square 
 = 15 * 15 --definição do operador (+) 
 = 225 --definição do operador (*) 
 
Estas duas sequências de reduções ilustram duas políticas de escolha de redução, 
conhecidas como innermost e outermost em grafos de redução, respectivamente. 
Na primeira delas, em cada passo de redução, foi escolhido o redex mais interno, ou 
seja, o redex que não continha qualquer outro redex interno a ele. Já na segunda 
sequência de reduções, optou-se pela escolha do redex mais externo, ou seja, um 
redex que não estava contido em qualquer outro. A redução outermost em grafos 
de redução é referenciada normalmente como lazy evaluation e a redução innermost 
como eager evaluation. 
 
Avalie as sub-expressões abaixo através das duas sequências de avaliação. Se não 
for possível realizar completamente a redução por alguma das sequências, 
justifique o porquê. 
 
a) snd (square 16, square 9) 
b) (+) 3 fst (12, loop 7) 
c) nlist (3+4) 
d) last (dlist 5 9) 
 
23. Dada a função f abaixo, a expressão f [1..] [2..] entra em loop? Justifique, 
explicando o porquê. 
 
f :: [Int] -> [Int] -> Int 
f (a:as) (b:bs) = a + b + head as + head bs 
 
24. Considere os seguintes tipos definidos em Haskell: 
 
data Termo = Constante Bool | Binaria Op Termo Termo | Unaria Op Termo 
data Op = E | OU | NEG 
 
Implemente uma função avaliadorLogico :: Termo -> Bool que avalie o Termo dado 
como parâmetro. 
 
Exemplo: 
Main> avaliadorLogico (Binaria OU (Unaria NEG (Constante True)) (Binaria OU 
(Constante False) (Constante True))) 
 
True 
 
25. Uma pilha é uma estrutura de dados em que todas as operações de inserção e 
remoção são realizadas pela mesma extremidade denominada topo. Geralmente, 
para manipular uma pilha, utilizam-se as operações push (insere um novo elemento 
no topo da pilha), pop (remove o elemento do topo da pilha) e top (acessa/retorna o 
elemento do topo da pilha). 
 
Crie os tipos algébricos polimórficos Pilha1 (utilizando apenas tipos recursivos) e 
Pilha2 (utilizando apenas listas) que podem ser exibidos. Implemente também as 
operações push1, pop1 e top1 que manipulam o tipo Pilha1 e push2, pop2 e top2 
que manipulam o tipo Pilha2. 
 
Caso a pilha esteja vazia e seja utilizada alguma das operações pop ou top, encerre 
a execução do programa e exiba a mensagem de erro: “Pilha vazia!”. 
 
26. Implemente um tipo algébrico polimórfico e recursivo Array que pode ser 
exibido. Um Array pode não conter nada ou conter um elemento de um tipo 
qualquer e outro Array do mesmo tipo. (O tipo algébrico Array não pode ser 
implementado por uma lista). 
 
Implemente também as funções: 
- alloc, que recebe um inteiro n e um elemento de um tipo qualquer s e retorna um 
Array de n posições todas com o valor s; 
- assign, que recebe um inteiro i, um elemento de um tipo qualquer s e um Array a e 
retorna o Array a com o valor do elemento da posição i substituído pelo valor do 
elemento s; 
- index, que recebe um inteiro i e um Array a e retorna o valor do elemento da 
posição i do Array a; 
- fromList, que recebe uma lista l de um tipo qualquer s e retorna um Array a do 
mesmo tipo contendo todos os elementos da lista l; 
- toList, que recebe um Array a de um tipo qualquer s e retorna uma lista l do 
mesmo tipo contendo todos os elementos do Array a. 
 
Para as funções assign e index, caso o índice do Array passado não contenha 
nenhum elemento, ou o tamanho do Array seja menor que o índice, deverá ser 
exibida uma mensagem de erro. 
 
27. Em Haskell, uma classe é uma coleção de tipos para os quais um conjunto de 
funções está definido. Por exemplo, os tipos que admitem comparação (se são 
iguais ou diferentes) entre os seus membros pertencem a classe Eq, os tipos que 
admitem uma ordenação de seus membros pertencem a classe Ord, etc. 
 
Para incorporar um novo tipo a uma classe, é necessário criar uma nova instância da 
classe e definir explicitamente cada função para os elementos do novo tipo. 
 
Compreendendo isso, crie uma instância da classe Funtor, mostrada abaixo, para o 
tipo algébrico Maybe t (já definido no arquivo “Prelude.hs”). Onde Funtor é uma 
classe que lida com tipos algébricos polimórficos de apenas um parâmetro. 
 
class Funtor d where 
 map' :: (t -> s) -> [d t] -> [d s] 
 filter' :: (t -> Bool) -> [d t] -> [d t] 
 foldl1' :: (t -> t -> t) -> [d t] -> d t 
 foldr1' :: (t -> t -> t) -> [d t] -> d t 
 (==>) :: (t -> d s) -> d t -> d s 
 (<==) :: d t -> (t -> d s) -> d s 
 
Exemplos: 
Main> map' (*10) [Just 1, Just 2, Just 3, Nothing, Just 10] 
[Just 10, Just 20, Just 30, Nothing, Just 100] 
 
Main> map' (<4) [Just 1, Just 2, Just 3, Nothing, Just 10] 
[Just True, Just True, Just True, Nothing, Just False] 
 
Main> filter' (<4) [Just 1, Just 2, Just 3, Nothing, Just 10] 
[Just 1, Just 2, Just 3] 
 
Main> foldl1' (^) [Just 2, Nothing, Just 2, Just 3] 
Just 64 
 
Main> foldr1' (^) [Just 2, Nothing, Just 2, Just 3] 
Just 256 
 
Main> foldr1' (*) (tail [Just 2]) 
Nothing 
 
Main> foldr1'(+) [Just 1] 
Just 1 
 
Main> foldl1' (+) [Just 1] 
Just 1 
Main> (\x -> Just(x^2+6)) ==> (Just 2) 
Just 10 
 
Main> Just “tenis” <== (\x -> Just (head x)) 
Just 't' 
 
 
28. Crie o tipo algébrico polimórfico Conj que pode ser exibido e que é 
representado por uma lista ordenada (de forma crescente) e sem repetições de 
elementos (semelhante a um conjunto de elementos). Crie, também, uma classe 
chamada OprConj que contenha as funções de união, diferença, interseção e 
diferença simétrica de conjuntos (ou seja, o conjunto dos elementos que pertencem 
a apenas um dos conjuntos). 
 
Em seguida, instancie o tipo Conj para a classe OprConj e implemente as funções 
dessa classe de forma que as de interseção e diferença simétrica utilizem 
necessariamente e apenas as funções de união e diferença. 
 
Os conjuntos resultantes de qualquer uma dessas operações devem sempre estar 
ordenados e não possuir elementos repetidos. Utilize alguma função de ordenação 
e/ou limite o tipo do conjunto às classes Eq e Ord, se necessário. 
 
29. Crie uma função que dado o nome de um arquivo e uma palavra imprime na 
tela o conteúdo das linhas do arquivo que essa palavra se encontra. 
 
30. Crie um programa que descobre o seu login a partir do seu nome e uma 
informação caso tenha número no login. O seu nome e a checagem de número deve 
ser passado pela entrada padrão (teclado) e a saída deve ser exibida no console. 
Após informar o seu nome, o programa deve perguntar se o seu login possui 
número, o número deve ser informado ou informe 0 caso não possua número. 
 
Exemplos: 
Main> main 
Informe seu nome completo: 
Alvaro Arthur Canto Sabino de Miranda Costa 
Caso tenha numero, informe (ou 0 caso nao tenha): 
0 
Seu login eh: aacsmc 
 
 
 
 
 
 
Main> main 
Informe seu nome completo: 
Gustavo de Oliveira Feitosa 
Caso tenha numero, informe (ou 0 caso nao tenha): 
0 
Seu login eh: gof 
 
Main> main 
Informe seu nome completo: 
Ihago Henrique Lucena e Silva 
Caso tenha numero, informe (ou 0 caso nao tenha): 
0 
Seu login eh: ihls 
 
Main> main 
Informe seu nome completo: 
Dino da Silva Sauro 
Caso tenha numero, informe (ou 0 caso nao tenha): 
3 
Seu login eh: dss3