BCC222 – Programação Funcional
Prof. José Romildo Malaquias
DECOM UFOP 2012/2
Lista de Exercícios
Programando com Listas
Exercise 1
Defina a função isIn :: Eq a => a -> [a] -> Bool que dados um valor e uma lista,
retorna verdadeiro se o valor está na lista e falso caso contrário.
Exemplos:
isIn 1 [1,2,3]
; True
isIn 2 [1,5,4]
; False
isIn ’e’ "Haskell" ; True
Exercise 2
Defina a função strip :: Eq a => [a] -> [a] -> [a] que dadas duas listas, retira
da segunda todos os elementos que ocorrem na primeira.
Exemplos:
strip [1,5] [1,2,5,5,3,5,1] ; [2,3]
strip "a" "batata"
; "btt"
Exercise 3
Em certas variações da escrita árabe usadas no dia a dia é comum a omissão da representação gráfica das vogais. Em muitos casos isso pode tornar difícil pronunciar, ou
até mesmo descobrir, uma palavra que não é previamente conhecida pelo leitor. Alguns
pesquisadores que estão traduzindo textos em árabe pediram ajuda ao departamento de
computação de uma universidade. Pede-se que se crie um programa que liste todas as
possíveis palavras que podem ser obtidas de uma sequência de consoantes, usando como
base um dicionário.
1. Defina a função ordSubList :: String -> String -> Bool que retorna verdadeiro
se somente se todas as consoantes da segunda lista, incluindo repetições, ocorrem
na primeira lista, na mesma ordem. Exemplos:
ordSublist "vsc" "vasco"
; True
ordSublist "sdd" "saude"
; False
ordSublist "sdd" "saudade" ; True
Dica: Use a função definida no exercício 2.
2. Usando a função definida no exercício 1, defina a função matches :: [String] > String -> [String] que recebe uma lista de palavras e uma sequência de consoantes e retorna uma lista de possíveis palavras representadas pelas consoantes.
Exemplos: Suponha o seguinte dicionário:
dic = ["arara","arreio","haskell","puxa","peixe",
"pixar","pixe","vaca","vacuo","velho","vermelho","vicio"]
matches dic "rr" ; ["arara","arreio"]
matches dic "vc" ; ["vaca","vacuo","vicio"]
1
Exercise 4
Em Haskell é muito comum pensar em programas sobre listas usando um padrão de
projeto produtor / consumidor. Essencialmente pode-se dividir o programa em duas partes, uma que constrói uma lista de valores e outra que consome a lista produzindo um
valor. Nos exercícios a seguir empregue esta técnica.
1. Defina a função primeFactors :: Int -> [(Int,Int)] que fatora um número inteiro em uma lista de pares (fator,frequência).
Exemplos:
primeFactors 8 ; [(2,3)]
primeFactors 42 ; [(2,1),(3,1),(7,1)]
Dica: Construa primeiro, a função primes :: Int -> [Int] que retorna a lista de
todos os fatores primos de um número. Exemplos:
primes 8 ; [2,2,2]
primes 42 ; [2,3,7]
primes 50 ; [2,5,5]
Em seguida defina a função countFactors :: [Int] -> [(Int,Int)] que conta a
ocorrência de cada fator. Exemplos:
countFactors [2,2,2]
; [(2,3)]
countFactors [2,2,3,5,5,5] ; [(2,2),(3,1),(5,3)]
2. [Opcional] Que propriedade de teste podemos usar para uma rápida verificação de
que este programa está correto? Defina esta propriedade e teste seu programa com
quickCheck.
Exercise 5
Uma lista pode ser dividida em sublistas, com base em elementos especiais chamados
marcadores que dizem quando começa uma lista e quando acaba outra.
1. Defina a função splitToken :: Eq a => a -> [a] -> [[a]] que recebe um valor
e uma lista e retorna uma lista de listas utilizando o valor dado como marcador.
Exemplos:
splitToken
splitToken
splitToken
splitToken
splitToken
2
3
0
’
’
[1,2,3,4,2,5,67,8,9,0,3]
[1,2,3,4,2,5,67,8,9,0,3]
[0,1,2,0,3,4,0,0]
’ "Haskell is cool"
’ "cool"
;
;
;
;
;
[[1],[3,4],[5,67,8,9,0,3]]
[[1,2],[4,2,5,67,8,9,0],[]]
[[],[1,2],[3,4],[],[]]
["Haskell","is","cool"]
["cool"]
2. Defina a função joinToken :: a -> [[a]] -> [a] que recebe um valor e uma lista
de listas e retorna a concatenação das sublistas usando o primeiro parâmetro como
separador.
Exemplo:
joinToken ’ ’ ["this","is","a","test"] ; "this is a test"
Exercise 6
Defina a função group :: Eq a => [a] -> [[a]] que agrupa elementos semelhantes
em sublistas.
Exemplo:
group [2,3,3,2,1,4,4,4] ; [[2],[3,3],[2],[1],[4,4,4]]
2
Exercise 7
Defina a função splitHalf :: [a] -> ([a],[a]) que divide uma lista em duas, de
tamanho iguais (ou com diferença de apenas um elemento no caso de uma lista de tamanho
impar).
Exemplo:
splitHalf [1,2,3,4] ; ([1,2],[3,4])
Exercise 8
Considere a seguinte função:
divList
:: Int -> Int -> [Int]
divList n k
| mod n k == 0 = k : divList (div n k) k
| k < n
= divList n (k+1)
| otherwise
= []
1. O que esta função faz?
2. Usando esta função e a função group do exercício 6, defina factorate :: Int > [(Int,Int)] que fatora um inteiro positivo.
Exemplo:
factorate 490 ; [(2,1),(5,1),(7,2)]
3. [Opcional] Como esta função poderia ser testada? Elabore um teste com quickCheck para verificar que sua função está correta.
Exercise 9
Uma tripla (x, y, z) de números inteiros positivos é chamada pitagórica se x2 + y 2 = z 2 .
Usando list comprehension, defina uma função pyths :: Int -> [(Int,Int,Int)] que
mapeia um inteiro n a uma lista de todas as triplas pitagóricas componentes no intervalo
[1..n].
Por exemplo:
pyths 5 ; [(3,4,5),(4,3,5)]
Exercise 10
Um número inteiro positivo é perfeito se ele igual à soma de todos os seus fatores, excluindo o próprio número. Usando list comprehension, defina uma função perfects :: Int -> [Int] que retorna a lista de todos os números perfeitos de zero até
um dado limite.
Por exemplo:
perfects 500 ; [6,28,496]
Exercise 11
O produto escalar de dois vetores v e w de tamanho n é dado pela soma dos produtos
dos elementos correspondentes:
v·w =
n−1
X
(vi × wi )
i=0
Usando list comprehension, defina uma função que retorna o produto escalar de dois
vetores representados por listas.
3
Exercise 12
O problema das n rainhas consiste em posicionar em um tabuleiro de xadrez n × n, n
rainhas de modo que cada rainha não ataque as demais. Uma rainha pode atacar qualquer
outra que esteja na mesma linha, coluna, ou nas mesmas diagonais. Considere que a
representação da solução será feita por meio de uma lista de pares (Linha, Coluna), de
coordenadas das rainhas.
1. Defina a função ataca :: (Int,Int) -> [(Int,Int)] -> Bool que dada uma posição e uma lista de posições diz se a primeira posição ataca qualquer uma das posições
da lista.
Exemplos:
ataca (3,2) [(1,2),(2,4)] ; True
ataca (2,2) [(1,3)]
; True
ataca (3,1) [(1,2),(2,4)] ; False
2. Usando list comprehension defina a função nqueens :: Int -> [[(Int,Int)]] que
dado o tamanho de um tabuleiro, retorna todas as possíveis soluções para a instância
dada do problema.
Exemplo:
nqueens 4 ; [[(4,2),(3,4),(2,1),(1,3)],[(4,3),(3,1),(2,4),(1,2)]]
4