Haskell
Programação Funcional
Diego Lima
Rubem Moreira
Funções - Recursão
• Problema: somar os elementos de uma lista
– sumList :: [Int] -> Int
• Solução: Recursão
– caso base: lista vazia []
• sumList [] = 0
– caso recursivo: lista tem cabeça e cauda
• sumList (a:as) = a + sumList as
Funções - Recursão
sumList [2,3,4,5]
= 2 + sumList [3,4,5]
= 2 + (3 + sumList [4,5])
= 2 + (3 + (4 + sumList [5]))
= 2 + (3 + (4 + (5 + sumList [])))
= 2 + (3 + (4 + (5 + 0)))
= 14
Exemplo
• Obter os n primeiros elementos de uma lista
– primeirosN :: [Int] -> Int -> [Int]
• Verificar se um elemento pertence a lista
– pertence :: Int -> [Int] -> Bool
Exemplo
• filtragem: apenas os números de uma string
– digits :: String -> String
• soma de uma lista de pares
– sumPairs :: [(Int,Int)]->[Int]
Exemplo
SORT
• Insere um elemento na lista verificando se [e
menor que o próximo.
– ins :: Int -> [Int] -> [Int]
Ordena uma lista de Int
• iSort :: [Int] -> [Int]
Polimorfismo
• Funções que recebem um tipo genérico
• Mesma definição usada para vários tipos
myZip :: [t] -> [u] -> [(t,u)]
myZip (a:as) (b:bs) = (a,b):zip as bs
myZip [] [] = []
Exemplo
• Função myLength
– myLength :: [t] -> Int
• Operador concatenação se iguais (lista)
– (&&&) :: [t] -> [t] -> [t]
Polimorfismo
• Utilização das classes Eq (igualdade entre tipos
genéricos) e Ord (comparação entre tipos genéricos)
pertence :: Eq t => t -> [t] -> Bool
maior :: Ord t => [t] -> t
Definições Locais
Resolução bottom-up e top-down
• sumQuadrados :: Int -> Int -> Int
sumQuadrados a b = sqA + sqB
where sqA = a * a
sqB = b * b
sumQuadrados a b = sq a + sq b
where sq x = x * x
Definições Locais
Resolução bottom-up e top-down
• sumQuadrados :: Int -> Int -> Int
sumQuadrados a b = let sqA = a*a
sqB = b*b
in sqA + sqB
sumQuadrados a b = let sq z = z*z
in sq a + sq b
CASE
firstDigit :: String -> Char
firstDigit st = case (digits st) of
[] -> '\0'
(a:as) -> a
IF THEN ELSE
ehStringTal :: String -> Int -> Bool
ehStringTal str a = if str == "oi" then True
else if str == "joao" then
if a == 3 then False
else True
else False
EXERCICIOS
• maior: recebe uma lista de números e retorna o
maior. obs.: não usar a função max
– maior :: [Int] -> Int
• gera_sequencia: recebe um número inteiro n
positivo e retorna a lista [1, -1, 2, -2, 3, -3, ... n, -n]
– gera_sequencia :: Int -> [Int]
EXERCICIOS
• rodar_esquerda: recebe um número natural,
uma lista e retorna uma nova lista onde a
posição dos elementos mudou como se eles
tivessem sido "rodados” ex.:
• (rodar_esquerda 0 '(a s d f g)) ==> (a s d f g)
(rodar_esquerda 1 '(a s d f g)) ==> (s d f g a)
• (rodar_esquerda 3 '(a s d f g)) ==> (f g a s d)
(rodar_esquerda 4 '(a s d f g)) ==> (g a s d f)
EXERCICIOS