01 intro programacao funcional

Prévia do material em texto

Notação: Programação baseada 
em definições
answer :: Int
answer = 42
greater :: Bool
greater = (answer > 71)
yes :: Bool
yes = True
Definição de Funções
square :: Int -> Int
square x = x * x
allEqual :: Int -> Int -> Int -> Bool
allEqual n m p = (n == m) && (m == p)
maxi :: Int -> Int -> Int
maxi n m | n >= m = n
 | otherwise = m
Aplicação de Funções
square 5 -- = 25
square(5) -- = 25
allEqual 1 2 3 -- = False
allEqual(1,2,3) -- ERRO!!!
allEqual(1) (2) (3) -- = False
maxi 24 645 -- = 645
Exemplo
Em um sistema de controle de vendas:
• suponha vendas semanais dadas pela função
vendas :: Int -> Int
• total de vendas da semana 0 à semana n?
vendas 0 + vendas 1 + ... + vendas (n-1) + vendas n
totalVendas :: Int -> Int
totalVendas n 
| n == 0 = vendas 0
| otherwise = totalVendas (n-1) + vendas n
Recursão
• Definir caso base, i.e. valor para fun 0
• Definir o valor para fun n 
usando o valor de fun (n-1)
Este é o caso recursivo.
maxVendas :: Int -> Int
maxVendas n
 | n == 0 = vendas 0
 | otherwise = maxi (maxVendas (n-1))
 (vendas n)
Exercícios
• Defina uma função que, dado um valor 
inteiro s e um número de semanas n, 
retorna quantas semanas de 0 a n tiveram 
vendas iguais a s.
Listas
• Coleções de objetos de um mesmo tipo.
• Exemplos:
[1,2,3,4] :: [Int]
[(5,True),(7,True)] :: [(Int,Bool)]
[[4,2],[3,7,7,1],[],[9]] :: [[Int]]
[’b’,’o’,’m’] :: [Char] 
”bom” :: [Char]
• Sinônimos de tipos:
type String = [Char]
• [] é uma lista vazia de qualquer tipo
• Estruturas de dados recursivas!
Listas vs. Conjuntos
• A ordem dos elementos é relevante
[1,2] /= [2,1]
assim como
“fernando” /= “odnanref”
• Duplicação de elementos também importa
[True,True] /= [True]
O construtor de listas (:)
• Outra forma de escrever listas:
[5] é o mesmo que 5:[]
[4,5] é o mesmo que 4:(5:[])
[2,3,4,5] é o mesmo que 2:3:4:5:[]
• (:) é um construtor polimórfico:
 (:) :: Int -> [Int] -> [Int]
 (:) :: Bool -> [Bool] -> [Bool]
 (:) :: t -> [t] -> [t]
Listas
• [2..7] = [2,3,4,5,6,7]
• [-1..3] = [-1,0,1,2,3]
• ['a'..'d'] = ['a','b','c','d']
• [2.8..5.0] = [2.8,3.8,4.8]
• [7,5..0] = [7,5,3,1]
• [2.8,3.3..5.0] 
 = [2.8,3.3,3.8,4.3,4.8] 
Exercícios
• Quantos itens existem nas seguintes listas?
 [2,3] [[2,3]] 
• Qual o tipo de [[2,3]]?
• Qual o resultado da avaliação de 
[2,4..9] 
[2..2] 
[2,7..4]
[10,9..1] 
[10..1]
[2,9,8..1]
Funções sobre listas
• Problema: somar os elementos de uma lista
sumList :: [Int] -> Int
• Solução: Recursão
–sumList as 
 | as == [] = 0
 | otherwise = (head as) +
 sumList (tail as)
Avaliando
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
Exercícios
• Defina estas funções sobre listas 
– dobrar os elementos de uma lista
double :: [Int] -> [Int]
– membership: se um elemento está na lista
member :: [Int] -> Int -> Bool
– filtragem: apenas os números de uma string
digits :: String -> String
– somar os elementos de duas listas
sumPairs :: [Int]->[Int]—>[Int]
Casamento de Padrões
• Permite usar padrões no lugar de variáveis, na 
definição de funções:
 maxVendas :: Int -> Int
maxVendas 0 = vendas 0
maxVendas n = maxi (maxVendas (n-1))
 (vendas n)
totalVendas :: Int -> Int 
totalVendas 0 = vendas 0
totalVendas n = totalVendas (n-1) + 
 vendas n
Casamento de padrões: listas
// devolve o maior elemento da lista
maiorLista :: [Int] -> Int
maiorLista [] = minBound :: Int
maiorLista [x] = x
maiorLista (x:xs) 
 | x > maiorLista xs = x
 | otherwise = maiorLista xs
Apenas construtores podem ser usados para casar 
padrões!!!
Casamento de Padrões: mais 
exemplos
myNot :: Bool -> Bool
myNot True = False
myNot False = True
myOr :: Bool -> Bool -> Bool
myOr True x = True
myOr False x = x
myAnd :: Bool -> Bool -> Bool
myAnd False x = False
myAnd True x = x
Regras para Padrões
• Todos os padrões (esquerda) devem ter o 
mesmo tipo
• Os casos devem ser exaustivos
• não é obrigatório  funções parciais
• Não deve haver ambiguidade
• ordem dos padrões usada para resolver conflitos
Exercícios
• Implemente o algoritmo QuickSort, usando apenas o 
que foi visto em sala de aula
Exercícios
• Implemente uma função que, dado um número inteiro 
N, retorne uma lista de inteiros com os N primeiros 
números pares da sequência de Fibonacci.
• Crie um função que recebe uma lista de inteiros e 
retorna a lista ordenada em função da soma de seus 
digitos(crescente):
Prelude> ordenar [5,12,70,8,25,3,150]
[12,3,5,150,70,25,8]
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 16
	Slide 19
	Slide 20