lista 2 2013 1

Prévia do material em texto

2ª Lista de Exercícios de Paradigmas de Linguagens Computacionais
Professor: Fernando Castor
 
Monitores:
Ciência da computação: Alberto Costa Jr. (arcj), Diego Aragão (dca), Hugo Bessa (hrba), João Victor Leite 
(jvfl), Luana Martins (lms7), Luiz Fernando Sotero (lfss2), Vítor Antero (vham)
 
CIn-UFPE – 2013.1
Disponível desde: 20/06/2013
Entrega: 08/07/2013
A lista deverá ser respondida em dupla. A falha em entregar a lista até a data estipulada implicará na
perda de 0,25 ponto na média da disciplina para os membros da dupla. Considera-se que uma lista na
qual menos que 8 das respostas estão corretas não foi entregue. A entrega da lista com pelo menos 12
das questões corretamente respondidas implica em um acréscimo de 0,125 ponto na média da disciplina
para os membros da dupla. Se qualquer situação de cópia de respostas for identifcada, os membros de
todas as duplas envolvidas perderão 0,5 ponto na média da disciplina. O mesmo vale para respostas
obtidas a partir da Internet. As respostas deverão ser entregues exclusivamente em formato texto ASCII
(nada de .pdf, .doc, .docx ou .odt) e deverão ser enviadas para o monitor responsável por sua dupla, sem
cópia para o professor. Devem ser organizadas em arquivos separados, um por questão, entregues em
um único formato compactado, ou seja, um único arquivo zipado contendo as respostas para todas as
questões. Caso a dupla não tenha monitor responsável ainda, siga as instruções descritar na lista 1 para
alocar a turma a algum monitor.
 
1) Defna três tipos algébricos:
-Elemento: com cinco construtores (Fogo, Vento, Trovao, Terra, Agua).
-Carta: com apenas um construtor (Card, este terá um valor do tipo Elemento, e um Int
representando a força da carta).
-Jogador: com apenas um construtor (Player, este terá um Int representando um ID, uma lista de
Cartas, uma função Elemento -> Int que representa a afnidade que este jogador tem com os
diversos elementos de carta, e um Int representando a pontuação).
Crie Instâncias de Show para Elemento e Carta, e Instâncias de Eq, Ord e Show para Jogador. Depois crie
uma função (partida :: [Jogador] -> [Jogador]) que simule uma partida de cartas entre jogadores, a cada
rodada desta partida os jogadores compararam as forças de suas cartas(as cartas do topo de cada
Jogador) acrescidas ou decrescidas do retorno de suas funções de afnidade(em relação ao elemento da
carta do topo), os jogadores que tiverem a maior força da rodada incrementam em 1 sua pontuação,
depois disso cada jogador descarta a carta que estava no topo e inicia-se uma nova rodada. Ao fnal da
partida (quando todos os jogadores não tiverem mais cartas) retorne a lista de jogadores em ordem
decrescente de pontuação.
Obs.: É garantido que na entrada da função todos os jogadores terão a mesma quantidade de cartas.
2) Crie a função annexer que dada uma função e uma lista de funções, retorne uma nova lista de funções
com a primeira “anexada” às funções da lista. Isto é, cada função f’ devolvida deverá funcionar quase
que como as funções f do segundo argumento (a lista de funções), exceto que f’ aplica a função g do
primeiro argumento de annexer após a aplicação de f. 
annexer :: (b -> c) -> [a -> b] -> [a -> c]
Inclua também em sua resposta pelo menos três exemplos de entradas e saídas em comentário.
3) Defna as seguintes funções:
setFilters :: (a->b->Bool) -> [a] -> [(b->Bool)], que é responsável por gerar a lista de funções parciais que
alimentarão specifcFilter, através da aplicação do seu primeiro argumento a cada um dos elementos do
segundo.
specifcFilter :: [(a->Bool)] -> [a] -> [a], que aplica as funções aos elementos correspondentes da lista
dada como entrada, eliminando os que não passarem de seus fltros especifcos
setMaps :: (a->b->c) -> [a] -> [(b->c)], que é responsável por gerar a lista de funções parciais que
alimentarão specifcMap, através da aplicação do seu primeiro argumento a cada um dos elementos do
segundo.
specifcMap :: [(a->b)] -> [a] -> [b], que aplica as funções aos elementos correspondentes da lista dada
como entrada.
specifcApply :: [(a->Bool)] -> [(a->b)] -> [a] -> [b], que aplicar todas as funções que aparecem em seu
segundo argumento, transformando os elementos do terceiro. A função que aparece na i-ésima posição
do segundo argumento é aplicada ao elemento na i-ésima posição do terceiro. Em seguida, specifcApply
fltra elementos resultantes da transformação descrita acima usando os predicados correspondentes no
primeiro argumento. 
*Main> a = setFilters (>) [10,20,29]
*Main> b = setMaps (+) [2,4,8]
*Main> specifcApply a b [7,21,10]
[9,18] -- porque 10 é maior que (2+7) e 29 é maior que (8+10)
4) Faça o que é pedido a seguir:
(a) Determine os tipos das expressões abaixo:
(a.1) foldr (+).(.).map
(a.2) (foldr).(.)$(!!)
(b) Explique informalmente e apresentando exemplos o funcionamento das funções a seguir:
(b.1) foldl.foldr
(b.2) filter.foldr (>)
(b.3) map.(+)
(b.4) \x -> map foldr $ [(+), (*), div, mod, subtract]
Nos itens acima, caso seja útil, antes tente determinar os tipos das expressões. 
Obs.: Lembre-se que se você apenas descobrir os tipos via GHCi, não estará se preparando
para as avaliações. 
5) Crie a função search que dado um grafo direcionado e dois nós do grafo, retorne a seguinte função
(Int -> Bool), tal que se o grafo tiver um caminho do primeiro nó ao segundo nó, ela retorna True.
O caminho a ser percorrido em busca do segundo nó será defnido pelo argumento 'Int'. 
Caso este seja igual a 1, a busca deverá ser feita por largura, caso seja 2, será por profundidade.
Vale resaltar que caso o referido argumento não seja nenhum desses, a função retornará a string
"Exception", através da função 'error'.
Poderá ser utilizada a seguinte defnição de grafos:
data (Eq t) => Grafo t = Graph [t] [(t,t)]
Tal que a primeira lista do construtor Graph é uma lista de vértices e a segunda lista é uma lista de
arestas, onde o primeiro nó é a origem e o segundo é o destino.
6) Defna o tipo recursivo Tree que represente uma árvore binária de busca não-balanceada onde cada
nó guarda tanto um código númerico quanto um valor de um tipo polimórfco (o payload do nó)
pertencente à classe Show. Crie então duas funções de manipulação de nós: insertNode e searchNode
para inserção e busca de um nó na árvore, respectivamente. A primeira deve incluir o nó com o código
numérico e o payload passados como argumentos na árvore fornecida como argumento. A escolha do
local onde o nó será inserido depende apenas do código numérico. A função searchNode recebe o
código do nó procurado e a árvore e devolve o payload do nó correspondente, se existir. Se não existir,
essa função deve devolver Nothing (um valor do tipo Maybe). Escreva uma função, multiSearchNode,
que, dados uma lista de códigos numéricos e uma árvore, obtém os payloads correspondentes a cada
um dos códigos fornecidos, caso existam. A função multiSearchNode deve devolver Nothing caso algum
dos itens procurados não exista e a lista de payloads obtidos (em um valor do tipo Maybe) caso todos
existam. 
Crie também a função printTree que deve retornar uma função (Int -> [String]), que dado o tipo da busca
(defnido pelo argumento “Int”) retorne a representação desta árvore em uma lista de Strings, com base
em seus payloads. 
Para o valor 1 como argumento “Int” a lista deve representar a árvore em pré-ordem e para o valor 2,
pós-ordem.
7) Crie uma função que recebe uma lista de função binárias, uma lista de elementos do tipo do primeiro
parâmetro e um valor do tipo do segundo parâmetro das funções binárias. A função applyAll :: [a -> b ->
c] -> [a] -> b -> [c] aplica o terceiro parâmetro a todas as funções parcialmente aplicadas geradas pelo
produto cartesiano dos dois primeiros parâmetros.
*Main> apply [(+),(-),(*),subtract] [1..5] 10
[11,12,13,14,15,-9,-8,-7,-6,-5,10,20,30,40,50,9,8,7,6,5]8) A recursão de cauda é uma técnica de recursão que faz menos uso de memória durante o processo de
empilhamento, devido ao fato de que em uma recursão de cauda, não é necessário guardar o stack
frame relativo a cada chamada de função. Utilizando estes conceitos faça uma nova solução para esta
questão:
Quantos quadrados diferentes existem em um quadriculado NxN(para N>=1)? Crie uma função : : Int -> 
Int que responda essa pergunta.
Exemplo p/ N = 2 a resposta é 5.
*Main> function 2
5
*Main> function 1
1
*Main> function 8
204
9) Ao perceber a importância de recursão de cauda para a efciência de programas, um aluno de PLC
decidiu implementar uma typeclass chamada TRtools com 4 funções que são muito usadas no meio
acadêmico. As funções escolhidas pelo aluno foram: fatorial, fbonacci, sumTR e multTR. As duas últimas
operam em listas e retornam a soma e a multiplicação dos elementos de uma lista, respectivamente.
Você deve criar uma instância da classe TRTools para o tipo Integer e implementar as quatro funções.
Lembre-se: suas soluções devem utilizar explicitamente recursão de cauda, objetivando efciência.
10) Escreva um programa que leia um texto de um arquivo defnido pelo usuário, e depois pergunte se o
usuário deseja cifrá-lo ou decifrá-lo, fazendo em seguida o que o usuário decidir. A cifra utilizada neste
programa deve ser a de césar (ROT13), e o arquivo de saída deve se chamar "out.txt". As palavras de
entrada devem ser apenas minúsculas, e não devem conter números ou símbolos. Sendo qualquer
entrada inválida (seja opção ou o texto de entrada) deve haver o texto “Opcao invalida” no arquivo de
saída.
Digite o nome do arquivo:
in.txt
Digite 1 para cifrar o documento, e 2 para decifrá-lo.
1
Fim do programa!
Ex de entradas e saídas:
in.txt
abc
trolololo
trolololo abc nop
out.txt
nop
gebybybyb
gebybybyb nop abc
11) Considere o tipo algébrico abaixo:
data (Eq t) => Tree t = Node t (Maybe (Tree t)) (Maybe (Tree t)) deriving Show
Crie as seguintes funções para manipular esse tipo como são descritas abaixo:
inOrder: Dado uma Tree retorna uma lista de tipo t.
preOrder: Dado uma Tree retorna uma lista de tipo t.
posOrder: Dado uma Tree retorna uma lista de tipo t.
insertNodeTree: Dado um tipo t e uma Tree retorna uma Tree adicionada de um nó com o elemento de
tipo t, em uma árvore binária.
depthFirst: Dado uma Tree retorna uma lista de tipo t, percorrendo a árvore em profundidade.
12)Infelizmente pokémons não existem na vida real, mas para deixar a vida das pessoas mais divertida
você deve criar uma simulação do mundo pokémon. Crie um tipo algébrico que simule os pokémons da
seguinte forma: cada pokémon possui um nome (String), um nível(Int), uma quantidade de pontos de
vida (Int), e uma lista de quatro ataques (tupla de funções que mudam o hp dos pokémons ). 
Quando os pontos de vida de um pokémon chegam a 0(zero) ou negativo, o pokémon desmaia.
Além do tipo algébrico você deve criar:
1. Uma função batalha que repete rodadas até que um dos pokemons desmaie;
2. Uma função rodada que recebe dois pokemons e simula uma rodada entre eles (escolhendo
ataques aleatórios ).
OBS1.: A cada rodada deve ser impresso na tela que golpes foram usados por quem em quem e que
dano eles causaram. Também deverá ser impresso uma mensagem avisando que a batalha foi fnalizada
e qual dos pokémons ganhou.
OBS2.: Quando os pontos de vida de um pokémon chegam a 0(zero) ou negativo, o pokémon desmaia e
a batalha acaba.
OBS3.: Utilize a função randomRIO :: Random a => (a, a) -> IO a da biblioteca System.Random para gerar
números aleatórios. 
13) Escreva um programa que lê entradas do usuário até ele acertar o número correto. O programa
deverá gerar um número aleatório e indicar ao usuário se o chute dele foi maior ou menor. Quando o
chute for correto, o programa também deve imprimir a quantidade de tentativas válidas feitas.
Utilize a função randomRIO :: Random a => (a, a) -> IO a da biblioteca System.Random para gerar
números aleatórios. 
Escolha um numero entre 1 e 100 (inclusive)
-5
Escolha um numero entre 1 e 100 (inclusive)
50
Quase lá! Sua escolha foi menor que a resposta
Escolha um numero entre 1 e 100 (inclusive)
75
Quase lá! Sua escolha foi menor que a resposta
Escolha um numero entre 1 e 100 (inclusive)
87
Ainda nao foi dessa vez! Sua escolha foi maior que a resposta!
Escolha um numero entre 1 e 100 (inclusive)
81
Quase lá! Sua escolha foi menor que a resposta
Escolha um numero entre 1 e 100 (inclusive)
84
Parabens! Voce acertou com 5 tentativas
14) Defna um tipo de dados TreeState que implementa uma computação que modifca uma árvore
mutável (em outras palavras, TreeState é uma instância da classe Monad). Reescreva então as funções
insertNode e searchNode da questão 6 para que as duas passem a devolver valores do tipo TreeState. As
modifcações, neste caso, vão muito além de apenas modifcar os tipos das funções, claro. :) Feito isso,
forneça exemplos de uso dessas funções. Essa questão é muito útil para ajudar a entender o projeto
que vocês terão que fazer!