EL-cap2-funcional-notasAula-130416-22h22

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
2.2.*
2.2 Linguagens de Programação Funcional 
Em vez disso, as linguagens de PROGRAMAÇÃO FUNCIONAL baseiam-se na 
TEORIA DAS FUNÇÕES MATEMÁTICAS
Fortemente afetadas pela 
arquitetura dos computadores convencionais
Até agora lidamos com as linguagens de PROGRAMAÇÃO ORIENTADA A COMANDO, 
chamadas de IMPERATIVAS
Ghezzi
Jazayeri

*
2.2. Linguagens de Programação Funcional 
A motivação para linguagens funcionais 
e sim os seguintes aspectos:
Como uma linguagem de programação 
pode dar um melhor suporte à 
composição de componentes independentes?
Qual é a unidade de decomposição 
mais apropriada de um programa ?
não é a eficiência da execução
2.2.*
Ghezzi Jazayeri
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
Nas LPs imperativas, as UNIDADES DE DECOMPOSIÇÃO são as funções e os procedimentos, 
que podem causar efeitos colaterais, 
nas estruturas globais que comunicam-se entre si
Com Tipos Abstratos de Dados 
há a tentativa de modularizar um programa, 
para limitar o escopo dos efeitos colaterais, 
pelo empacotamento de dados e de operações, 
nas UNIDADES ENCAPSULADAS
A programação funcional baseia-se 
nas funções matemáticas, 
operando sobre valores e 
produzindo valores, sem qqr efeito colateral 
?
?
sem variável ?
*
2.2.*
2.2. Linguagens de Programação Funcional 
 em seguida vamos apresentar 
a linguagem de programação funcional: 
HASKELL
2
Ghezzi Jazayeri
 Inicialmente, serão abordadas as 
principais diferenças da 
programação funcional, 
comparadas aos conceitos básicos 
da programação imperativa
Para salientar mais ainda essas diferenças,
as funções matemáticas serão comparadas com 
as funções das linguagens imperativas
1
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
As linguagens de programação funcional primitivas,
começando por LISP, 
adotavam escopo e tipagem dinâmicas
Scheme é um dialeto de LISP, 
que adotou escopo estático na linguagem
Mais tarde, linguagens funcionais, tais como ML, Haskell, adotaram não somente escopo estático 
mas também tipagem forte
Haskell é puramente funcional, 
sem variável e sem comando de atribuição. 
Assim, não inclui recursos imperativos e 
não produz efeitos colaterais. 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
O estado de um programa imperativo 
é mantido em variáveis de programa
Essas variáveis são associadas a alocações de memória, que são caracterizadas por:
um endereço (l-value) e 
um valor armazenado (r-value) 
2.2.1 Características de Linguagens Imperativas
O acesso ao valor de uma variável pode ser 
direto via seu l-value ou 
indireto via o r-value de uma outra variável
APONTADOR
As linguagens de programação imperativa 
são caracterizadas por três conceitos:
variáveis, atribuição e seqüência de execução
1-VARIÁVEIS
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
As linguagens de programação imperativa 
são caracterizadas por três conceitos:
variáveis, atribuição e seqüência de execução
2.2.1 Características de Linguagens Imperativas
O valor de uma variável é alterado na execução de um comando de atribuição 
O comando de atribuição introduz uma ordem de dependência no programa: 
o valor de uma variável pode ser diferente antes e depois da execução de um comando de atribuição
Os efeitos em um programa, então,
DEPENDEM DA ORDEM em que 
os comandos são escritos e executados
2-ATRIBUIÇÃO
ATRIBUIÇÃO e seqüência de execução
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
Na matemática, variáveis são amarradas a valores 
e uma vez amarradas, não trocam de valores
2.2.1 Características de Linguagens Imperativas
Assim, o valor de uma função INDEPENDE dos conceitos da programação imperativa, como por exemplo, A ORDEM DA EXECUÇÃO DOS COMANDOS
Uma função matemática define um mapeamento de um valor de domínio para um valor de faixa
3-SEQÜÊNCIA de execução
As linguagens de programação imperativa 
são caracterizadas por três conceitos:
variáveis, atribuição e seqüência de execução
? Resposta à frente
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Características de Linguagens Imperativas
um conjunto de pares ordenados que relaciona cada elemento no domínio com um único correspondente elemento na faixa 
descrita como algoritmo que especifica 
como computar os valores da faixa 
para um valor de domínio em uma 
DETERMINADA SEQÜÊNCIA DE PASSOS
FUNÇÃO na PROGRAMAÇÃO IMPERATIVA é

Lembrando que as linguagens de programação imperativa são caracterizadas por três conceitos:
variáveis, atribuição e seqüência de execução
FUNÇÃO MATEMÁTICA é
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
REPETIÇÃO (LOOP) é uma outra característica das linguagens imperativas, usada, freqüentemente, para computar os valores desejados
2.2.1 Características de Linguagens Imperativas
Os loops são usados, por exemplo, para: 
 varrer uma seqüência de alocações de memória (p/ex. arrays)
 acumular o valor de uma dada variável
Em contraste, em funções matemáticas, 
os valores são computados pela aplicação de função
RECURSÃO é usada no lugar de ITERAÇÃO 
COMPOSIÇÃO DE FUNÇÃO é usada para 
construir funções mais poderosas
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
Por causa das diferentes características
2.2.1 Características de Linguagens Imperativas
As LINGUAGENS IMPERATIVAS 
são chamadas de 
As LINGUAGENS FUNCIONAIS 
são chamadas de
BASEADAS EM ESTADO 
ou
ORIENTADA A COMANDO
BASEADAS EM VALORES
ou 
APLICATIVAS
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
Uma função é uma 
REGRA PARA MAPEAMENTO DE MEMBROS 
de um conjunto domínio 
para um conjunto faixa
Ex. função quadrado poderia mapear elementos do conjunto inteiro p/conjunto natural
CONCEITO
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
A assinatura especifica o domínio e a faixa
A regra de mapeamento especifica o valor da faixa associado a cada valor de domínio 
A definição de uma função é constituída de duas partes: 
			uma assinatura e 
			uma regra de mapeamento
CONCEITO
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
Atenção: na literatura aparece 
o símbolo  para denotar “é definida como”,
mas aqui está sendo usado o símbolo = adotado em Haskell.
DEFINIÇÃO
Então, encontra-se também:
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
função nomeada quadrado, acima, definida
como o mapeamento de elementos do conjunto inteiro p/conjunto natural
nas definições de função, por convenção, 
a assinatura é omitida se 
domínio e faixa são implícitos no contexto
símbolo = em Haskel significa “é definida como”
n é um parâmetro, que representa 
qualquer membro do conjunto do domínio
DEFINIÇÃO
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
Uma vez definida uma função, ela pode ser aplicada a qualquer membro do conjunto domínio
Esse elemento, chamado o argumento, substitui o argumento da definição
A aplicação produz (ou resulta, ou retorna) o elemento associado na faixa
No momento da aplicação, um elemento particular do domínio é especificado
APLICAÇÃO
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
A substituição é puramente textual 
Se a definição da regra de mapeamento 
contém aplicações,
elas são aplicadas na seqüência até ser alcançada uma expressão que possa ser avaliada para produzir o resultado da aplicação original
? 2 pgs à frente
APLICAÇÃO
quadrado (2)
produz o valor 4 
de acordo com a sua definição
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
O parâmetro n é uma variável matemática
diferente de uma variável de programa
Em contraste, a variável de programa, no paradigma imperativo, pode assumir diferentes valores durante o curso da execução de um programa
Na definição da função, n representa 
qualquer membro do conjunto domínio
Na aplicação da função, é dado um valor específico,
que nunca é trocado
APLICAÇÃO
? 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
Novas funções podem ser criadas pela 
COMBINAÇÃO DE OUTRAS
A forma mais comum de combinação de funções é a COMPOSIÇÃO
Se uma função F é definida como a composição de duas funções G e H, escrita como F = G o H,
a aplicação de F é definida pela 
aplicação de H e então 
a aplicação de G para 
chegar finalmente ao resultado
COMBINAÇÃO DE FUNÇÕES
*
2.2.*
2.2. Linguagens de Programação Funcional 
Nas LPs convencionais, 
uma função é definida procedimentalmente
A regra de mapeamento de um valor do domínio para um valor de faixa é determinada em termos de passos que necessitam ser executados em uma certa ordem especificada pela estrutura de controle
Por outro lado, as funções matemáticas são 
DEFINIDAS APLICATIVAMENTE 
Muitas funções matemáticas são definidas recursivamente, i.e, a definição da função contém 
uma aplicação da própria função
Contraste entre convencionais e funcionais
Ghezzi Jazayeri
2.2.1 Funções na Matemática e na Programação
RECURSÃO
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
Por exemplo, a definição matemática padrão de fatorial de um número natural é
n! = if n = 0 then 1 else n* (n-1)! 
RECURSÃO
Muitas funções matemáticas são definidas recursivamente, i.e, a definição da função contém uma aplicação da própria função
Outro exemplo é a possibilidade de formular uma função recursiva p(n, i), de números naturais para booleano, que coopera para determinar se um número é primo prime (n) = if n = 2 then true else p(n, n div 2)
Essa função auxiliar p(n,i) produz true se n não tem 
divisor na faixa 2..i, 
p (n, i) = if (n mod i) = 0 
	 then false else if i = 2 then true else p (n, i-1)
p( n, i ) é recursiva
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Funções na Matemática e na Programação
RECURSÃO
função recursiva, de números naturais para booleano, que determina se um número é primo
prime (n)  if n = 2 then true else p(n, n div 2)
A função auxiliar p(n,i) produz true se n não tem 
divisor na faixa 2..i, 
p (n, i)  if (n mod i) = 0 
	 then false else if i = 2 then true else p (n, i-1)
p( n, i ) é recursiva
Notar como a chamada recursiva p (n, i-1) assume o papel da iteração adotada no loop de um programa imperativo
Recursão é uma técnica poderosa para solução de problemas, usada pesadamente em programação com funções
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
A programação funcional tem 
três componentes primários:
1) Um conjunto de objetos de dados
2) Um conjunto de funções embutidas
3) Um conjunto de formas funcionais
nas expressões 
(também chamadas funções de alta ordem) para a construção de novas funções
Obs.: Funções de alta ordem aceitam uma ou mais funções, como entrada/saída de uma função.
alta ordem?
*
Funções de alta ordem aceitam uma ou mais funções, como entrada/saída de uma função. 
Em matemática, também são conhecidas por operadores ou funções. 
Derivada no cálculo é um ex., pq mapeia uma função para outra. No cálculo lambda não tipado, todas as funções são de alta ordem. No cálculo lambda tipado, do qual a maioria das linguagens funcionais são derivadas, funções de alta ordem são geralmente aquelas com tipos que aparecem com mais de uma seta. 
Na programação funcional, funções de alta ordem que retornam outras funções, são ditas currificadas (curried). A função map encontrada em muitas LPs funcional é um exemplo de uma função de alta ordem. Ela tem como parâmetros uma função f e uma lista de elementos, e como resultado, retorna uma nova lista com f aplicada a cada elemento da lista. Outro tipo muito comum são funções de ordenação que aceitam uma função de comparação como um parâmetro, permitindo ao programador separar o algoritmo de ordenação das comparações dos itens a serem ordenados. Um exemplo disso é a função qsort C padrão. Outros exemplos de funções de alta ordem incluem fold, function composition, integração, e a função constant-function λx.λy.x.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
A programação funcional tem três componentes primários:
1) Um conjunto de objetos de dados
Tradicionalmente, as linguagens de programação funcional oferecem um mecanismo de estruturação de dados exclusivo de alto nível tal como uma lista ou um array
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
A programação funcional tem três componentes primários:
Essas funções tratam os objetos de dados básicos
2) Um conjunto de funções embutidas
Por exemplo:
As LPs funcionais oferecem um número de funções para construção de acesso a listas
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
A programação funcional tem três componentes primários:
Estilo de programação baseado no uso de funções
3) Um conjunto de formas funcionais nas expressões 
(também chamadas de funções de alta ordem) 
para a construção de novas funções
Todas as expressões são baseadas em funções (funções podem ser argumentos de outras funções)
Toda a programação é baseada na 
avaliação de expressões para gerar valores
(cada valor tem um tipo associado, que pode ser implícito)
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
A programação funcional tem três componentes primários:
Um exemplo bastante comum de uma expressão é a composição de função “°”
Outro exemplo comum é a redução de função
A forma funcional da expressão reduce aplica uma função binária pelos sucessivos elementos de uma seqüência
3) Um conjunto de formas funcionais nas expressões 
(também chamadas de funções de alta ordem) 
para a construção de novas funções
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
3) Um conjunto de formas funcionais (também chamadas de funções de alta ordem) para a construção de novas funções
A forma funcional reduce aplica uma função binária pelos sucessivos elementos de uma seqüência
Por exemplo:
 reducing + sobre um array produz a soma dos elementos do array
 reducing * sobre o array produz o produto dos elementos do array
Em APL, / é a forma funcional de redução (chamada operator), que precisa de uma operação como argumento
a redução soma pode ser executada por /+
a redução multiplicação pode ser executada por /*
Por 
exemplo
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
3) Um conjunto de formas funcionais 
(também chamadas de funções de alta ordem) para a construção de novas funções
As formas funcionais permitem que programadores definam novas funções como combinações de funções sem o uso explícito de estruturas de controle tais como comandos de iteração e condicionais
As funções são entidades de 1ª classe, porque podem ser:
passadas como parâmetros
retornadas como resultado 
armazenadas em estruturas de dados
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios
da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais: amarração e aplicação
1) Amarração é usada para associar valores a nomes
Dados e funções podem ser usados 
como valores
2) Aplicação é usada para computar novos valores
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
É um cálculo simples que pode ser usado 
para modelar, precisamente, 
o comportamento das funções 
pela definição 
das semânticas de amarração e aplicação 
Lambda Calculus
Alonzo Church desenvolveu 
Lambda Calculus em 1930 
como uma teoria de funções 
que oferece regras para 
a manipulação de funções 
de uma forma puramente sintática (textual) 
ver
gjm.lambook88
*
6.*
O desafio de resolver todas as questões matemáticas:
1936: Church
6. Máquinas de Turing
Todas as propostas sérias de um modelo de computação têm o mesmo poder, i.e, calculam as mesmas funções ou reconhecem as mesmas linguagens.
equivalência
*
6.*
Máquina de Turing mT
Modelo matemático do processo de computação
6. Máquinas de Turing
Pretende alcançar um modelo universalmente aceito!
Principal uso: demonstrar o que é ou não computável 
*
6.*
Tese de Church
1- Todos os modelos razoáveis de procedimento são equivalentes
6. Máquinas de Turing
2- Mas a mT revelou-se o modelo mais flexível para as demonstrações do que é ou não computável
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3.2 Lambda calculus: um modelo de computação por funções
2.2. 3 Princípios da programação funcional
Embora Lambda Calculus tenha surgido como um desvio da lógica matemática para prover um fundamento para a matemática, ela tem conduzido a ramificações consideráveis na teoria da linguagem de programação:
1) Embora Lambda Calculus tenha poder para representar todas as funções computáveis, a simplicidade de sua sintaxe e sua semântica traz um veículo excelente para o estudo do significado de conceitos de linguagem de programação
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3.2 Lambda calculus: um modelo de computação por funções
2.2. 3 Princípios da programação funcional
Embora Lambda Calculus tenha surgido como um desvio da lógica matemática para prover um fundamento para a matemática, ela tem conduzido a ramificações consideráveis na teoria da linguagem de programação:
2) Todas as linguagens de programação funcional podem ser vistas como uma variação sintática de Lambda Calculus, tal que suas sintaxe e implementação possam ser analisadas no contexto de Lambda Calculus 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3.2 Lambda calculus: um modelo de computação por funções
2.2. 3 Princípios da programação funcional
Embora Lambda Calculus tenha surgido como um desvio da lógica matemática para prover um fundamento para a matemática, ela tem conduzido a ramificações consideráveis na teoria da linguagem de programação:
3) Semântica denotacional, um dos primeiros métodos de especificação formal de linguagens, expressa suas definições usando as funções de alta ordem de Lambda Calculus
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3.2 Lambda calculus: um modelo de computação por funções
Lambda calculus é um cálculo simples que modela os aspectos computacionais de funções
O estudo de lambda calculus nos ajuda a compreender os elementos da programação funcional e o entendimento da semântica das linguagens de programação funcional, independentemente, dos detalhes de sintaxe de uma linguagem particular de programação funcional
2.2. 3 Princípios da programação funcional
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
 um simples identificador tal como x, ou uma constante tal como 3
2.2. 3 Princípios da programação funcional
 uma definição de função, com a 
forma (x.e), que representa a expressão e com x entendida como uma variável amarrada. A expressão e representa o corpo da função e x o argumento da função. A expressão e pode conter qualquer das três formas de expressão lambda: e1, e2 ou e3.
 uma aplicação de função com a forma (e1 e2), que representa a expressão e1 aplicada a expressão e2. 
Ex: função quadrado definida como (x.x*x) 
 função quadrado aplicada ao valor 2
((x.x*x)2)
2.2.3.2 Lambda calculus: um modelo de computação por funções
e2
e3
e1
Ex
Há 3 espécies de expressões em lambda calculus:
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
Parênteses podem ser omitidos de (e1 e2) e de (x.e) 
Na ausência de parênteses, na aplicação de função, a precedência de associação é da esquerda para a direita
aplicação de função tem precedência maior que definição de função 
Exemplo: x.y z significa (x.(y z))
2.2. Linguagens de Programação Funcional 
2.2.3.2 Lambda calculus: um modelo de computação por funções
2.2. 3 Princípios da programação funcional
Assim, e1 e2 e3 significa ((e1 e2) e3)
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
Uma variável que aparece numa definição de função F é dita livre em F se ela não é amarrada em F
Variáveis amarradas são como parâmetros formais numa definição de rotina e agem como variáveis locais
2.2. Linguagens de Programação Funcional 
2.2.3.2 Lambda calculus: um modelo de computação por funções
2.2. 3 Princípios da programação funcional
Variáveis livres são como variáveis não locais que serão amarradas em um nível mais externo 
Por ex, a definição de função x.xk define a função k-ésima potência 
com x como uma variável amarrada e 
k como uma variável livre
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
A sintaxe para expressões lambda mostra que 
a aplicação de função utiliza 
a forma de prefixo 
sendo a notação usual f(x) 
substituída por f x
2.2. Linguagens de Programação Funcional 
2.2.3.2 Lambda calculus: um modelo de computação por funções
2.2. 3 Princípios da programação funcional
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
Implicitamente foi assumido que as funções têm um só argumento, realmente, lambda calculus usa uma alternativa ingênua para funções com múltiplos argumentos. Todas as funções são reduzidas para funções de argumento único por meio de um mecanismo conceitual chamado currying (após o lógico Haskell B. Curry tê-la introduzido)
2.2. Linguagens de Programação Funcional 
2.2.3.2 Lambda calculus: um modelo de computação por funções
2.2. 3 Princípios da programação funcional
P/ex, podemos expressar a soma de 1 e 3, normalmente escrito como 1+3, ou 
na forma funcional, soma (1,3)
Na sintaxe de lambda calculus, 
escreveríamos: soma 1 3 
ou usando o operador +: + 1 3, que agrupa (+1) 3
A expressão (+1) denota a função que adiciona 1 ao argumento, no caso o valor 3.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2. 3 Princípios da programação funcional
Lambda calculus captura o comportamento de funções com um conjunto de regras de reescrita de expressões lambda
A reescrita de uma expressão modela um passo na computação de
uma função
2.2.3.2 Lambda calculus: um modelo de computação por funções
Para aplicar uma função a um argumento, nós reescrevemos a definição da função, substituindo ocorrências da variável amarrada pelo argumento para o qual a função está sendo aplicada 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.1 Princípios da programação funcional
A seguir, faremos:
uma revisão dos elementos básicos da programação funcional, usando a sintaxe de Haskell
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Supondo o seguinte trecho em Java, baseado em atribuição de variável, para soma de 1 a 100
Em Haskell, a codificação para soma de 1 a 100
int total = 0;
for (int i = 1; i <= 100; i++)
	total = total + i;
S1_100 :: Integer 
S1_100 = sum [1..100] 
- está baseada na função sum e na idéia de lista implícita
- o método de programação é aplicação de função
total muda 100 vezes
Especificada uma aplicação de sum ao argumento lista de 100 elementos.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
Em Haskell, notar que
o código:
S1_100 :: Integer 
S1_100 = sum [1..100] 
- está baseado na função sum e na idéia de lista implícita
- o método de programação é aplicação de função
Conseqüências da abordagem funcional:
Uma vez estabelecido o valor de s1_100
- tem um tipo definido (pode ser implícito)
- o valor não pode ser mudado
- o valor pode ser usado como argumento de funções
2.2.2 Haskell
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Uma pergunta que surge é 
SERÁ QUE É POSSÍVEL PROGRAMAR ?
SEM ITERAÇÕES
SEM EFEITOS COLATERAIS
SEM MUDAR O VALOR DE VARIÁVEIS
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Expressões
Em Haskell, 
as EXPRESSÕES são especificadas com os seguintes símbolos ou construções:
Constantes
Operadores
Aplicação de funções
Parênteses ( )
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Expressões
Constantes:
True
2009
28876543212125
12.589
‘b’
“cadeia”
[4,8,9]
Constantes
Operadores
Aplicação de funções
Parênteses ( )
Aplicação de Funções:
primo 53
seno 30
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Operadores
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Definições
-- PI
pi = 3.14159
Programador pode definir constantes e funções
-- área de círculo
area r = pi * r ^ 2
significa em lambda calculus “def perimetro = r.(2*pi*r)”
significa em lambda calculus “ def area = r.(pi*r^2)”
-- perímetro de círculo
perimetro r = 2 * pi * r
Uma aplicação: “perimetro 3”
Uma aplicação: “area 3”
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos básicos
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos em Haskell
Toda expressão deve ter um tipo associado
Tipos podem ser explícitos ou inferidos
sum :: Float -> Float -> Float
sum x y = x + y
sum2 :: Float -> Float
sum2 y = sum 2 y
perimetro :: Float -> Float
perimetro r = 2 * pi * r
area :: Double -> Double
area r = pi * r ^ 2
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tuplas
Haskell permite composição de tipos:
(Integer, Integer) -- pares de inteiros
(Integer, Char, Bool) – etc.
Em geral, (A, B) representa um tipo, cujo primeiro membro é do tipo A e o 
segundo membro é do tipo B.
O emprego de tuplas é uma estratégia para permitir o retorno de mais de um valor da função, que aparece no formato de tupla.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tuplas
Haskell permite composição de tipos:
(Integer, Integer) -- pares de inteiros
(Integer, Char, Bool) – etc.
Em geral, (A, B) representa um tipo, cujo primeiro membro é do tipo A e o segundo membro é do tipo B.
Exemplo de uma função que devolve os dois valores: a soma e a subtração de dois argumentos de entrada.
soma_e_sub :: (Int,Int) -> (Int,Int)
soma_e_sub (a,b) = (a+b, a-b)
EX. de execução:
Prelude> soma_e_sub (1,2)
(3,-1)
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Conjunto de definições de funções
quadr :: Int -> Int -- assinatura
quadr n = n * n -- regra de mapeamento
dobro :: Int -> Int
dobro n = 2 * n
dobrQuadr :: Int -> Int
dobrQuadr n = quadr ( dobro n )
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Funções
Uma função é um mapeamento de valores de um tipo em outro tipo
not :: Bool -> Bool
isDigit :: Char -> Bool
add :: (Int, Int) -> Int
add (x, y) = x + y
ou 
add x y = x + y
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Funções
Aplicação de funções em Haskell
f(x)
f(x,y)
f(g(x))
f(x, g(y))
f(x) g(y)multiplica
f(a,b) + cd
Matemática
Haskell
f x
f x y
f(g x)
f x (g y)
f x * g y
f a b + c * d
precedência de aplicação de funções é maior
www.dpi.inpe.br/cursos/cap365/funcional.ppt
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função Currificada
Voltando ao exemplo em Tuplas 
soma_e_sub (a,b) = (a+b, a-b)
aparece um único parâmetro, a tupla, que tem dois valores encapsulados.
Uma variação é transformar a versão acima em uma versão currificada, reescrevendo soma_e_sub (a,b) como:
soma_e_sub_curr :: Int -> Int -> (Int,Int)
soma_e_sub_curr a b = (a+b, a-b)
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Um exemplo mais abrangente de função currificada
f_nao_currificada (x,y,z,w) = x + y + z + w
f_currificada x y z w = x + y + z + w 
Alternativas permitidas para execução:
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Main> f_currificada 3 4 5 6
18
Main> (f_currificada 3) 4 5 6
18
Main> ((f_currificada 3) 4) 5 6
18
Main> (((f_currificada 3) 4) 5) 6
18
Main> ((((f_currificada 3) 4) 5) 6)
18
Main> f_nao_currificada (3, 4, 5, 6)
18
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função Currificada
Observações importantes
Uma função de n parâmetros pode ser contraída em uma função de um parâmetro.
f_nao_currificada (x,y,z,w) = x + y + z + w
f_currificada x y z w = x + y + z + w 
O modo como os passos podem ocorrer nas várias alternativas de execuções vistas foi possível devido ao fato dos parâmetros estarem livres entre si.
Vimos a transformação abstrata de várias somas de acordo com a associatividade da esquerda para a direita.
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função Currificada
Observações importantes
f_nao_currificada (x,y,z,w) = x + y + z + w
f_currificada x y z w = x + y + z + w 
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Main> f_currificada 3 4 5 6
18
Main> (f_currificada 3) 4 5 6
18
Main> ((f_currificada 3) 4) 5 6
18
Main> (((f_currificada 3) 4) 5) 6
18
Main> ((((f_currificada 3) 4) 5) 6)
18
Main> f_nao_currificada (3, 4, 5, 6)
18
Essa abstração, seguindo a associatividade esq./dir., em que o valor 3 foi o primeiro a ser avaliado e o valor 6 o último a ser avaliado, reforça o conceito de avaliação preguiçosa, em que nada é calculado até que seja efetivamente necessário.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função Currificada
Observações importantes
f_nao_currificada (x,y,z,w) = x + y + z + w
f_currificada x y z w = x + y + z + w 
Em outras palavras, 
na avaliação preguiçosa, transformações abstratas intermediárias foram adiadas, até que a disponibilidade dos termos numéricos fosse necessária na expressão.
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Main> f_currificada 3 4 5 6
18
Main> (f_currificada 3) 4 5 6
18
Main> ((f_currificada 3) 4) 5 6
18
Main> (((f_currificada 3) 4) 5) 6
18
Main> ((((f_currificada 3) 4) 5) 6)
18
Main> f_nao_currificada (3, 4, 5, 6)
18
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função Currificada
Observações importantes
A associatividade à esquerda é observada e para o caso de 4 argumentos em uma função f, note que: 
f_nao_currificada (x,y,z,w) = x + y + z + w
f_currificada x y z w = x + y + z + w 
Uma generalização para n argumentos é inferida.
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
f a b c d = ( f a ) b c d = ( ( f a ) b ) c d = ( ( ( f a ) b ) c) d 
Em outras palavras, toda função é aplicada ao seu primeiro argumento, à sua direita, depois, o resultado desta expressão avaliada é aplicada ao segundo argumento, e, assim, sucessivamente, até o último argumento na função.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função Currificada
Observações importantes
Finalmente, a função f_currificada tem uma equivalente em uma notação prefixada, pelas razões anteriores, que, em Haskell, pode ser escrita, como a seguir:
f_nao_currificada (x,y,z,w) = x + y + z + w
f_currificada x y z w = x + y + z + w 
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Execução para f_currif_2 3 4 5 6 na pag. seguinte
f_currif_2 x y z w = (+)((+)((+) x y) z) w 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função Currificada
Execução da função equivalente em uma notação préfixa
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Main> f_currif_2 3 4 5 6
18
Main> ((((f_currif_2 3) 4) 5) 6)
18 
f_currif_2 x y z w = (+)((+)((+) x y) z) w 
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
A indução matemática é apropriada para olhar a recursão
Indução Matemática é 
uma definição generalizada 
para um conjunto de objetos 
com uma propriedade comum
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
A indução matemática proporciona uma propagação típica 
da recursividade
Recursão
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Indução é 
uma definição generalizada 
para um conjunto de objetos 
com uma propriedade comum
Deve-se conhecer o caso trivial, 
geralmente, para n=0, n=1, 
que são os valores–base ou triviais
O passo seguinte é demonstrar que, 
para um n genérico, 
a propriedade indutiva mantém-se desde n-1
Recursão
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Então, para o termo n 
essa propriedade indutiva permanece válida, 
considerando que em n-1 era verdadeira
*
O conceito dessa idéia de indução é a base de toda a programação em Haskell, 
mas esses passos matemáticos 
são deixados a cargo do computador
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Para esses cálculos, 
uma propagação que começa de n 
é construída do fim para o início, 
até o caso trivial dessa regra recursiva
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Indução é 
uma definição generalizada 
para um conjunto de objetos 
com uma propriedade comum
Recursão
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
 Exemplo clássico de recursão, por meio de uma idéia indutiva
Soma dos n primeiros inteiros.
1 + 2 + 3 + ... + (n-1) + n, 
representado por soma
(n)
Recursão
soma (5) = 1 + 2 + 3 + 4 + 5 = 15
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
 Raciocínio p/ soma dos n primeiros inteiros 1+ 2 + 3 + 4 + ... + n
soma 1 = 1
Recursão
soma n = (soma (n-1)) + n
soma 2 = (soma 1) + 2
soma 3 = (soma 2) + 3
soma 4 = (soma 3) + 4
...
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
então soma (n) =
1 : n = 1
soma (n-1) + n : n > 1
vale 
para n-1, então, 
vale
para n
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Recursão
soma (n) =
1 : n = 1
soma (n-1) + n : n > 1
Observa-se uma soma repetitiva entre 
o último número com 
a soma acumulada até o número antecessor
regra indutiva geral: soma n = soma (n-1) + n
soma 1 = 1 soma n = soma (n-1) + n
aterramento (última ação da função): soma 1 = 1
O código em Haskell fica então, como a seguir:
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
 Outro exemplo clássico de recursão é o fatorial de um número inteiro.
raciocínio para fatorial de n:
Recursão
fatorial 0 = 1
fatorial n = (fatorial (n-1)) * n
fatorial 1 = (fatorial 0) * 1
fatorial 2 = (fatorial 1) * 2
fatorial 3 = (fatorial 2) * 3
...
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
então fatorial (n) =
1 : n = 0
fatorial (n-1) * n : n  1
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Cuidados com a Recursão
O aterramento da função deve aparecer antes da chamada da função recursiva geral.
 	Cuidado: caso se inverta, 
	ocorre uma seqüência infinita de chamadas.
regra indutiva geral: fatorial n = fatorial (n-1) * n
aterramento (última ação da função): fatorial 0 = 1
O código em Haskell fica então, como a seguir:

Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
fatorial 0 = 1 fatorial n = fatorial (n-1) * n
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Uso de guardas | 
para aterramento e regra geral
Uma guarda é uma condição lógica para que a definição da função seja executada
As guardas podem ser montadas, como ao lado:
função arg1 arg2 ...
|guarda_1 = expressão_1
|guarda_2 = expressão_2
...
|otherwise = expressão_n
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Nessa montagem, uma função pode possuir:
m args, n guardas c/ suas respectivas expressões, e um otherwise, que abrange as demais condições possíveis mas não declaradas.
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Exemplo com e sem uso de guarda, para a especificação de uma função que retorna quantos múltiplos de 7 há em x (no intervalo de 0 a n):
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
multi_7 0 = 0
multi_7 1 = 0 
multi_7 2 = 0
multi_7 3 = 0
multi_7 4 = 0
multi_7 5 = 0
multi_7 6 = 0
multi_7 7 = 1
multi_7 x = 1 + mult_7(x-7)
SEM USO
DE
GUARDAS
multi_7 7 = 1
multi_7 x 
 |(x>=0) && (x<=6) = 0
 |otherwise = 1 + multi_7 (x-7)
COM uso de Guardas
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Sem o emprego de guardas, são usadas muitas definições triviais. 
Exemplo com e sem uso de guarda, para a especificação de uma função que retorna quantos múltiplos de 7 há em x (no intervalo de 0 a n):
Com guarda, a definição da função fica contraída. 
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
No exemplo SEM uso de guardas, a variável amarrada x, ou seja, o argumento, na função multi_7, fez um casamento condicional com valores de 0 a 6, retornando 0, com 7, retornando 1, enquanto que para os demais valores, recursivamente segue na busca de mais múltiplos. 
multi_7 0 = 0
multi_7 1 = 0 
multi_7 2 = 0
multi_7 3 = 0
multi_7 4 = 0
multi_7 5 = 0
multi_7 6 = 0
multi_7 7 = 1
multi_7 x = 1 + mult_7(x-7)
multi_7 7 = 1
multi_7 x 
 |(x>=0) && (x<=6) = 0
 |otherwise = 1 + multi_7 (x-7)
COM
Exemplo com e sem uso de guarda, para a especificação de uma função que retorna quantos múltiplos de 7 há em x 	(no intervalo de 0 a n):
SEM
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
CASAMENTO DE PADRÕES
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Casamento de Padrão é 
um OUTRO recurso de alto nível 
para a declaração das diferentes condições, 
nas quais se baseiam as execuções 
das diferentes ações especificadas
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
CASAMENTO DE PADRÕES
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Casamento de Padrão é 
um OUTRO recurso de alto nível 
para a declaração das diferentes condições, 
nas quais se baseiam as execuções 
das diferentes ações especificadas
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
CASAMENTO DE PADRÕES - exemplo
data dia = Seg|Ter|Qua|Qui|Sex|Sab|Dom
...
dia_descanso::dia-> Bool
dia_descanso Sab = True
dia_descanso Dom = True
dia_descanso x = False 
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
A função dia_descanso é definida por uma série de casos.
Dependendo do valor, no argumento com o qual a função é invocada, o caso apropriado será selecionado.
Os casos são verificados seqüencialmente , do primeiro em diante. 
Pelo ex, vimos que há dois efeitos: 1) O argumento é amarrado ao padrão quando há casamento;
2) a ação é escolhida, baseada 
no argumento.
A variável amarrada (argumento) pode ser usada no mapeamento.
1
2
3
?
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
CASAMENTO DE PADRÕES
multi_7 0 = 0
multi_7 1 = 0 
multi_7 2 = 0
multi_7 3 = 0
multi_7 4 = 0
multi_7 5 = 0
multi_7 6 = 0
multi_7 7 = 1
multi_7 x = 1 + mult_7(x-7)
multi_7 7 = 1
multi_7 x 
 |(x>=0) && (x<=6) = 0
 |otherwise = 1 + multi_7 (x-7)
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Essa duplicação de código poderia ser evitada ? Sim.
Vamos ver exemplos interessantes de casamento de padrão, a seguir. 
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Exemplo didático para uso de casamento de padrões
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Notação com várias condicionais na mesma linha, para a função g equivalente a função f
COM Guardas
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
A função h é outro exemplo equivalente às funções f e g, acrescentando, ao casamento de padrão, o emprego de variável anônima, identificada por _
h 7 _ _ = 10
h _ 8 _ = 20
h _ _ 9 = 30
h _ _ _ = 0
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
EQUIVALENTES
?
emprego de variável anônima, identificada por _
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
h 7 _ _ = 10
h _ 8 _ = 20
h _ _ 9 = 30
h _ _ _ = 0
Haskell Uma Abordagem Prática
– Claudio C. Sá e Márcio F. da Silva 
Main> f 7 8 9
Main> 10
Main> f 17 8 9
Main> 20
Main> f 17 18 9
Main> 30
Main> f 17 18 19
Main> 0
Main> g 7 8 9
Main> 10
Main> g 17 8 9
Main> 20
Main> g 17 18 9
Main> 30
Main> g 17 18 19
Main> 0
Main> h 7 8 9
Main> 10
Main> h 17 8 9
Main> 20
Main> h 17 18 9
Main> 30
Main> h 17 18 19
Main> 0
f definido com guardas, g com casamento de padrão e guarda e h com casamento de padrão juntamente com variável anônima
f, g e h são equivalentes
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
As execuções mostram que f, g e h são equivalentes:
h 7 _ _ = 10
h _ 8 _ = 20
h _ _ 9 = 30
h _ _ _ = 0
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Main> f 7 8 9
Main> 10
Main> f 17 8 9
Main> 20
Main> f 17 18 9
Main> 30
Main> f 17 18 19
Main> 0
Main> g 7 8 9
Main> 10
Main> g 17 8 9
Main> 20
Main> g 17 18 9
Main> 30
Main> g 17 18 19
Main> 0
Main> h 7 8 9
Main> 10
Main> h 17 8 9
Main> 20
Main> h 17 18 9
Main> 30
Main> h 17 18 19
Main> 0
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos Compostos com Tuplas
Novos tipos podem ser construídos com o uso da função type pré-definida em Haskell. Lembra typedef em C.
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Exemplo: uma tupla contendo as estações climáticas
type Cadeia = String –-cadeia caracteres
type Nomes_4 = (Cadeia,Cadeia,Cadeia,Cadeia)
f_nomes_estacao :: Nomes_4
f_nomes_estacao=(“Inverno”,”Outono”,”Primavera”,”Verao”)
selec_inverno (x,_,_,_) = x
selec_outono (_,x,_,_) = x
selec_prima (_,_,x,_) = x
selec_verao (_,_,_,x) = x
As funções genéricas de seleção empregaram casamento de padrão com 
var. anônima
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos Compostos com Tuplas
Observar que: 
Cadeia empregou String,
Nomes_4 empregou Cadeia, e
f_nomes_estacao empregou Nomes_4
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
type Cadeia = String –-cadeia caracteres
type Nomes_4 = (Cadeia,Cadeia,Cadeia,Cadeia)
f_nomes_estacao :: Nomes_4
f_nomes_estacao=(“Inverno”,”Outono”,”Primavera”,Verao”)
selec_inverno(x,_,_,_)= x
selec_outono (_,x,_,_)= x
selec_prima (_,_,x,_)= x
selec_verao (_,_,_,x)= x
4 funções genéricas, 
sem assinatura, o
tipo será inferido, 
no argumento, 
na hora da aplicação
As funções de seleção empregaram casamento de padrão com var. anônima
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos Compostos com Tuplas
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
f_nomes_estacao=(“Inverno”,”Outono”,”Primavera”,Verao”)
selec_inverno(x,_,_,_)= x
selec_outono (_,x,_,_)= x
selec_prima (_,_,x,_)= x
selec_verao (_,_,_,x)= x
Main> f_nomes_estacao
(“Inverno”,”Outono”,”Primavera”,Verao”)
Main> selec_inverno f_nomes_estacao
“Inverno”
Main> selec_verao f_nomes_estacao
“Verao”
Main> selec_outono (“João”,”Pedro”,”Augusto”,”Marcio”)
“Pedro”
A última execução deve-se a inferência na hora da aplicação com o uso de funções genéricas
Execuções com as funções genéricas definidas acima
?
Funções
genéricas
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos Compostos com Tuplas
Novos tipos podem ser construídos com o uso da função type pré-definida em Haskell. Lembra typedef em C.
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
type Peso = Float 
type Idade = Int
type Pessoa = (String, Idade, Peso, String)
f_joao, f_maria :: Pessoa –- assinatura p/lista de funções
f_joao = (“Joao Carlos”, 21, 67.543,“Volei”)
f_maria = (“Maria Lucia”,23,52.759, “Tenis”)
Exemplo: uma tupla contendo campos com tipos diferentes (lembra struct em C): nome, idade, peso e esporte favorito.
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos Compostos com Tuplas
Observar que 
Peso empregou Float
Idade empregou Int
Pessoa empregou um tupla c/ 
String, Idade, Peso e String
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
type Peso = Float 
type Idade = Int
type Pessoa = (String, Idade, Peso, String)
f_joao, f_maria :: Pessoa –- assinatura p/lista de funções
f_joao = (“Joao Carlos”, 21, 67.543,“Volei”)
f_maria = (“Maria Lucia”,23,52.759, “Tenis”)
f_joao e f_maria são funções constantes, que iniciam conteúdos às suas tuplas. 
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos Compostos com Tuplas
Funções que extraem ou relacionam partes de uma tupla são especificadas usando casamento de padrões, realizado, pela seleção do campo desejado na tupla de 4, de modo que a mesma tenha um tipo compatível com o que foi definido nesta função.
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
f_joao, f_maria :: Pessoa –- assinatura p/lista de funções
f_joao = (“Joao Carlos”, 21, 67.543,“Volei”)
f_maria = (“Maria Lucia”,23,52.759, “Tenis”)
selec_nome :: Pessoa -> String
selec_idade :: Pessoa -> Idade
selec_peso :: Pessoa -> Peso
selec_esporte :: Pessoa -> String
selec_nome (n,i,p,e) = n
selec_idade (n,i,p,e) = i
selec_peso (n,i,p,e) = p
selec_esporte (n,i,p,e) = e
assinaturas
Mapeamentos
de funções genéricas
*
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tipos Compostos com Tuplas
Execuções com as 
novas funções
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
selec_nome :: Pessoa -> String
selec_idade :: Pessoa -> Idade
selec_peso :: Pessoa -> Peso
selec_esporte :: Pessoa -> String
Main> f_joao
(“Joao Carlos”, 21, 67.543,“Volei”)
Main> f_maria
(“Maria Lucia”,23,52.759, “Tenis”)
Main> selec_nome f_joao
“Joao Carlos”
selec_nome (n,i,p,e) = n
selec_idade (n,i,p,e) = i
selec_peso (n,i,p,e) = p
selec_esporte (n,i,p,e) = e
f_joao, f_maria :: Pessoa –- assinatura p/lista de funções
f_joao = (“Joao Carlos”, 21, 67.543,“Volei”)
f_maria = (“Maria Lucia”,23,52.759, “Tenis”)
Main>selec_esporte(“Luis Paulo”,23,70.345, “Surf”)
“Surf”
Main> selec_peso f_maria
52.759
Main> selec_idade f_joao
21
Main> selec_esporte f_maria
“Tenis”
argumento é do tipo Pessoa
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Listas
Lembrando
Lista é uma estrutura de dados que representa uma coleção de objetos homogêneos em seqüência
O acesso a um elemento da lista para qualquer operação acima, conta sempre com o seu cabeçalho. 
Lista permite que os seus elementos sejam consultados, alterados, incluídos em uma posição desejada, ou removidos.
As vezes, como forma de melhorar o desempenho, pode-se utilizar outros apontadores, além do cabeçalho, o corrente (último acessado), anterior, posterior e o último.
A partir do cabeçalho, os elementos podem ser percorridos seqüencialmente até o alcance desejado.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
A execução de programas funcionais é baseada sobre dois mecanismos fundamentais:
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Listas
Lembrando
Em Haskell, a lista é considerada como tendo duas partes: a cabeça (head) e o rabo (tail).
[a,b,c,d] - se esses são os elementos de uma lista, a cabeça é o elemento a, o primeiro da lista. 
A cabeça da lista é sempre o primeiro elemento. 
Por meio desse primeiro
elemento é feito o acesso aos elementos restantes da lista. 
A notação de listas é uma seqüência de elementos, separados por vírgula e delimitados por [ ].
Exemplos na página seguinte.
Uma lista pode não conter elementos, assim, a lista é considerada vazia [ ].
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Listas
Ex. de listas com elementos homogêneos 
Letras::[Char] --lista de caracteres
Letras = [‘x’,‘a’,’y’,‘b’]
Inteiros::[Int] --lista de inteiros
Inteiros = [7, 32, 9, 64]
Booleanos::[Bool] –-lista de booleanos
Booleanos = [False, True, False, True]
Tuplas::[(Int, Char)] –-lista de tuplas
Tuplas=[(4,’x’),(35,’z’),(99,’t’)]
Listas::[[Char]] –-lista de listas
Listas=[“Maria”,[‘a’,’x’,’b’,’y’]]
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Principais funções pré-definidas para listas
Para construir uma lista, basta simplesmente usar o operador : e a lista inicialmente vazia [ ]
Prelude> 0:[1,2]
[0,1,2]
Prelude> 5:[1,2,3,4]
[5,1,2,3,4]
Prelude> 5:1:2:3:4:[]
[5,1,2,3,4]
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Operador : inclui um elemento no início da lista 
:
:
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Tratando lista e o operador :
Todas as funções que tratam listas exercem uma ação recursiva sobre ela própria.
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
:
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Notas para o caso geral de funções recursivas complementadas para o caso de listas
1- Enquanto a chamada à função não encontrar a sua definição de parada (aterramento), ela segue empilhando as instâncias pendentes em uma pilha virtual de chamadas sobre tal função.
2- No momento em que a função encontra um critério de parada (aterramento), ela é considerada bem sucedida e com um valor instanciado. 
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
A partir desse ponto, vai sucedendo-se o desempilhamento de cada chamada pendente, com o valor retornado, sendo empregado no ponto da expressão em que houve a chamada.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Notas para o caso geral de funções recursivas complementadas para o caso de listas
3- A cada chamada recursiva, há uma nova instância de ativação, e um casamento de padrão é definido para o argumento da função.
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Tais argumentos definem o padrão de como deve se dar o casamento.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Notas para o caso geral de funções recursivas complementadas para o caso de listas
4- A ação de separar a cabeça da lista do tail (resto) é também conhecida pelos termos: escalpelar ou decapitar a lista. 
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Esta separação da cabeça da lista faz parte de todos os procedimentos recursivos, a fim de que se possa acessar qualquer outro elemento da lista, no momento que chegue a sua vez de ser a cabeça da lista.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Validação de uma estrutura do tipo lista
1- Uma lista vazia é uma lista
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
Estas definições são recorrentes e validam se uma estrutura é do tipo lista. 
As listas autodefinem-se com o conceito clássico de listas com os seguintes axiomas:
2- Uma sublista também é uma lista
A definição de que uma sublista é uma lista, depende da definição primária ou base, 
de que uma lista vazia é uma lista.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
1- Uma lista vazia é uma lista
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
lista[ ] = True -- mapeamento 1
lista (a:x) = lista x -- mapeamento 2
Reescrevendo em Haskell as seguintes definições:
2- Uma sublista também é uma lista
A variável a, neste caso, é a cabeça da lista, e, quanto a x, representa o corpo da lista.
O mapeamento 1 utiliza um padrão que casa somente com a lista vazia, que é o final da recursão, depois de todos os elementos terem sido decapitados, na condição de cabeça da lista.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
1- Uma lista vazia é uma lista
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
lista[ ] = True -- função 1
lista (a:x) = lista x -- função 2
Reescrevendo em Haskell as seguintes definições:
2- Uma sublista também é uma lista
O mapeamento 2 casa com qualquer estrutura que use o operador : , quer dizer, 
qualquer lista de no mínimo um elemento. 
Por exemplo, a lista [1,2,3,4] pode ser reescrita pela expressão 1:(2:(3:(4:[]))), e, a partir desta, os possíveis casamentos de padrão ocorrem.
:
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
lista[ ] = True -- mapeamento 1
lista (a:x) = lista x -- mapeamento 2
Execuções de aplicações, empregando lista
Main> lista [1,2,3,4]
True
Main> lista [‘a’]
True
Main> lista [‘a’,1,2]
ERROR – Cannot infer instance
*** Instance : Num Char
*** Expression : lista [‘a’,1,2]
Main> lista [2,4,[6,8]]
ERROR – Cannot infer instance
*** Instance : Num [a]
*** Expression : lista [2,4,[6,8]]
tipos

tipos

*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.3 Princípios da programação funcional
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função que devolve o comprimento de uma lista
1- O comprimento da lista vazia é zero
compto [] = 0 -- mapeamento 1
compto (a:x) = 1 + compto x –- função 2
2- O comprimento de uma lista (a:x) é dada por 
1 + o comprimento da sublista x
3- a variável a é a cabeça da lista e x representa o corpo (resto) da lista
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
compto [] = 0 --função 1
compto (a:x) = 1 + compto x –-função 2
A função 1 faz parar a recursão
A função 2 define a recursão, em que a cada passo, a cabeça da lista é separada, é somado 1 e novamente chamada compto com o novo tail (resto) obtido da lista, que novamente, na nova chamada vai ter sua cabeça separada, somado +1 e resubmetido o novo tail da lista. 
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
a variável a é a cabeça da lista e 
x representa o tail (resto) da lista
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Função que devolve o comprimento de uma lista
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
primeiros 0 = []
primeiros _ [] = [] 
primeiros n (a:x) = a : primeiros (n-1) x
Função que obtém os n primeiros elementos de 1 lista
Construída com uma estratégia que utiliza casamento de padrão
Main> primeiros 2 [2]
[2]
Main> primeiros 2 [2,3,4]
[2,3]
Main> primeiros 7 []
[]
possui duas condições de parada e uma regra geral recursiva.
Na regra geral , acontecem n recursões, cada uma tirando uma cabeça, para formar a lista resultante.
Na volta da recursão, concatenando cada cabeça com a sublista retornada.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
pertence p [] = False
pertence p (a:x) | p == a = True
 | otherwise = pertence p x
Função que verifica se um objeto pertence à lista
Main> pertence 1 [1,2,3]
True
Main> pertence 1 [3,2,3]
False
Main> pertence 1 []
False
A recursão prossegue até que: 
1) a lista tenha se resumido a uma lista vazia [ ], 
devido a decapitação em cada passo da sublista de 
entrada, retornando False;
2)o objeto seja encontrado na lista, retornando True. 
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
insere c [] = [c]
insere c (a:x) | c == a = a:x
 | otherwise = a : insere c x
Função que insere um objeto na lista, sem repetições, i.e, se já existir, então, não insere.
A recursão prossegue até que: 
a lista tenha se resumido a uma lista vazia [ ], quando 
retorna [c], uma lista com um objeto, o argumento c.
2) o argumento c coincida com uma cabeça a de uma sublista, 
retornando então a lista resultante da concatenação de a com 
a sublista x.
3)Em todas as voltas, 
cada cabeça a volta a fazer parte da lista,
pela concatenação com a lista retornada da chamada. 
Para que esse critério seja seguido, o objeto é inserido no final da lista, para que possam ser verificados todos os elementos da lista.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
insere c [] = [c]
insere c (a:x) | c == a = a:x
 | otherwise = a : insere c x
Testando a função que insere um objeto na lista, sem repetições, i.e, se já existir, então, não insere.
Main> insere 4 [1,2,3]
[1,2,3,4]
Main> insere 2 [1,2,3]
[1,2,3]
Main> insere 9 [1,2,3]
[1,2,3,9]
Para que esse critério seja seguido, o objeto é inserido no final da lista, para que possam ser verificados todos os elementos da lista.
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
maior_1 [a] = a
maior_1 (a:x)= if (a > (maior_1 x)) 
 then a
 else (maior_1 x)
Função que devolve o elemento de maior valor
São apresentadas três versões equivalentes
maior_2 [a] = a
maior_2 (a:b:x)|a > b = maior_2(a:x)
 |otherwise = maior_2(b:x)
maior_3 [a] = a
maior_3 (a:x)| a > (maior_3 x) = a
 |otherwise = (maior_3 x)
Decapita duas cabeças, 
1º e 2º elementos
a e b
*
Ghezzi Jazayeri
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
menor [a] = a
menor (a:c)|a < (menor c) = a
 |otherwise = menor c
Função que ordena uma lista
São empregadas duas funções: 
menor devolve o menor elemento de uma lista; 
remove_menor, devolve uma lista sem o menor
remove_menor[a] = []
remove_menor(a:c)|a ==(menor(a:c))= c
 |otherwise = a:remove_menor c
ordena_lista[] = []
ordena_lista [a] = [a] 
ordena_lista l = 
 (menor l):(ordena_lista(remove_menor l))
*
Ghezzi Jazayeri
2.2.3 Princípios da programação funcional
Operador == comparar duas listas 
Além de mostrar que é possível comparar duas listas, vemos que as duas formas de representar uma lista são equivalentes.
Prelude> [1,2,3] == (1:2:3:[])
True
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Algumas funções pré-definidas para listas
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
Ghezzi Jazayeri
2.2.3 Princípios da programação funcional
length - comprimento de uma lista
Lista vazia [] tem comprimento zero.
Prelude> length [2,7,3,5,4] 
5
Lista (a : x) é dada por 1 mais o comprimento da sublista x, que também é uma lista. 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Principais funções pré-definidas para listas
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
2.2.3 Princípios da programação funcional
++ - concatena duas listas
Prelude> [2,7,3,5,4] ++ [6,8]
[2,7,3,5,4,6,8]
head – primeiro elemento cabeça da lista
Prelude> head [2,7,3,5,4] 
2
last – último elemento da lista
Prelude> last [2,7,3,5,4] 
4
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Principais funções pré-definidas para listas
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva 
*
Ghezzi Jazayeri
2.2.3 Princípios da programação funcional
www.dpi.inpe.br/cursos/cap365/funcional.ppt 
tail – devolve uma lista sem o primeiro elemento
Prelude> tail [2,7,3,5,4]
[7,3,5,4]
init – lista sem o último elemento
Prelude> init [2,7,3,5,4] 
[2,7,3,5]
null – verifica se a lista está ou não vazia
Prelude> null [2,7,3,5,4] 
False
Prelude> null [] 
True
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.*
2.2. Linguagens de Programação Funcional 
2.2.2 Haskell
Principais funções pré-definidas para listas
*
Ghezzi Jazayeri
2.2.3 Princípios da programação funcional
reverse – devolve o reverso da lista
Prelude> reverse [2,7,3,5,4]
[4,5,3,7,2]
take – pega os n primeiros elementos da lista
Prelude> take 3 [2,7,3,5,4] 
[2,7,3]
drop – apaga os n primeiros elementos da lista
Prelude> drop 2 [2,7,3,5,4] 
[3,5,4]
2.2. Linguagens de Programação Funcional 
2.2.*
2.2.2 Haskell
Principais funções pré-definidas para listas
Haskell Uma Abordagem Prática – Claudio C. Sá e Márcio F. da Silva