Linguagem Funcional 2
Linguagem Funcional 2 - LF2



Estende LF1 com funções de alta
ordem
Uma função passa a ser um valor
O contexto inclui um único
componente:
• mapeamento de identificadores em
valores
Linguagem Funcional 2 - LF2


Portanto, o resultado da avaliação de
uma expressão pode ser uma função,
uma função pode ser argumento de
outra função, ...
Um programa é uma expressão
Explorando conceitos na LF2
O tipo função

Apesar de LF2 não possuir tipos explícitos,
adotamos a seguinte convenção quando for
necessário explicitar o tipo de uma função:
f: T1 ->T2 - indica que o argumento de f tem tipo T1 e o
resultado tem tipo T2
f: (T1 x ... x Tn) -> T - indica que f possui n argumentos de
tipos T1, ..., Tn, respectivamente, e resultado do tipo T

Observe que uma declaração da forma
f: ((T1 -> T2) x T3) -> T4
indica que f tem 2 argumentos: uma função (T1 ->
T2) e um outro do tipo T3; O resultado de f é do
tipo T4
Explorando conceitos na LF2
O tipo função

Como um outro exemplo, considere a declaração
f: T1 -> (T2 -> T3)

que indica que f tem 1 argumento (T1) e produz
como resultado uma função (T2 -> T3)
Observe que esta flexibilidade é uma
conseqüência de funções serem valores (cidadãs
de primeira classe)!
Explorando conceitos na LF2
Funções como parâmetros de
funções

Vários exemplos apresentados em sala
compara - compara dois elementos, fornecida uma
ordem
aplicação - aplica uma função dada a um argumento
dado
composição - aplica a composição de duas funções
dadas a um argumento dado
Explorando conceitos na LF2
Funções como resultado


A avaliação de uma função é o próprio texto
da função: fn x . x + 1 é um programa
(expressão) válido em LF2 cuja avaliação
retorna o próprio
Várias versões da função composição
apresentadas em sala: com dois, um e até
zero argumentos
LF2 permite currificação
(Currying)

Considere as seguintes definições para min
fun min x y = if (x <= y) then x else y
fun min’ x = fn y . min (x, y)

Observe que min é sempre aplicada a dois
argumentos e retorna o menor deles,
enquanto min’ pode ser aplicada só a um
argumento, retornando uma função que
espera o outro argumento.
LF2 permite currificação
(Currying)


Portanto, a expressão: min’(x) é
válida, mas min(x) não. Note que
(min’(x))(y) = min(x,y)
Tipos: min : (int x int) -> int
min´ : int -> (int -> int)
LF2 permite currificação
(Currying)

Um outro exemplo:
fun add x = fn y . (x + y)



Qual o tipo de add
O que as funções add 0 e add 1
computam?
Mais exemplos:
• As diversas versões de composição
apresentadas em sala
Polimorfismo


Por não ter tipos explícitos, funções em LF2
podem apresentar comportamento polimórfico
Por exemplo, a declaração
• Let fun Id x = x in ...

Permite que Id seja aplicada a qualquer
argumento (de qualquer tipo)
Mas cuidado! LF2 não é de fato polimórfica;
como não há verificação de tipos, certas
aplicações podem causar erro em tempo de
execução
Prova e Transformação de
Programas



Computação em LF2 (e em programação
funcional em geral) é baseada em reescrita de
termos
A computação (avaliação) de uma
expressão e resultar em um valor v é
também a prova da equação e = v
Portanto, além de ser um mecanismo de
computação, reescrita é um método de
dedução (largamente difundido)
Reescrita e Lógica Equacional



Teoria com igualdade que permite a
substituição do lado esquerdo pelo lado direito
de uma equação, e vice-versa.
Igualdade é uma relação de ordem: reflexiva,
simétrica e transitiva
Uma propriedade fundamental:
substitutividade:
 f: T1 T2; x, y: T1  (x = y)  (f x =
f y)
Mais sobre reescrita e lógica
equacional

Igualdade entre funções é definida por
extensionalidade
(f = g)  ( x  f(x) = g(x))
Provando equivalência entre
funções


Um exemplo simples usando apenas substituição
Considere as funções:
Suc x = x + 1
Pred x = x – 1
Id x = x

Provar que a composição de Suc e Pred
equivale a Id
Equivalência entre funções
recursivas

Considere a função
exp(x, 0) = 1
exp(x, n+1) = x * exp(x, n)
Provar:
(2)
exp(x, m+n) = exp(x, m) * exp(x, n)
Caso (0).
Caso (n+1).
(1)
Explorando Conceitos Adicionais
de Programação Funcional
Tipos estruturados de dados:
Listas

Coleção de elementos onde
• A ordem dos elementos é relevante
• A repetição “
“
“
“

Notação
•
•
•
•
•

[] : [T]
[1,2,3] : [int]
[[1,2],[3]] : [[int]]
[suc, pred] : [int  int]
1..5 : [int]
Qual o tipo das listas acima
Construtor de listas - cons (:)

A notação [x1,...,xn] é uma abreviação
para
x1 : x2 : ... : xn : []

Exemplos
1 : [] = [1]
1 : 2 : [3, 4] = [1, 2, 3, 4]


Qual o tipo de cons
cons pode ser usado em casamento de
padrão
Exemplos de funções sobre
listas

head e tail

Concatenação


head(x : xs) = x
tail(x : xs) = xs
[] ^^ ys = ys
(x : xs) ^^ ys = x : (xs ^^ ys)
Qual o tipo de ^^
Que propriedades ^^ satisfaz
Linguagem Funcional 3 – LF3


Implementa listas, mas não casamento de
padrão
head e tail em LF3 são operadores prédefinidos e não requerem parênteses
head xs
tail xs

Concatenação em LF3 também é um
operador pré-definido
xs ^^ ys
Padrão recursivo: fold

fold op a [x1,...,xn] = x1 op ...(xn-1 op
(xn op a))
fold op a [] = a
fold op a (x : xs) = x op (fold op a xs)
Defina operações soma e produto de uma
lista de elementos usando fold
Fold em LF3
let fun fold op a xxs =
if (xxs==[]) then a
else (let var x = head xxs, var xs = tail
op(x, fold(op,a, xs))) in …
xxs in
Outros padrões recursivos
map f [] =[]
map f (x : xs) = (f(x)) : map(f,xs)
filter p [] = []
filter p (x : xs) = x : filter(p,xs), if p(x)
= filter(p,xs), otherwise

Alguns exemplos
• map lengh [“PLP”, “ES”, “Redes”]
• filter positivo [-5, 3, -2, 0, 4]
onde positivo(x) = (x > 0)
Filter e Map em LF3
let fun filter p xxs =
if xxs == [] then []
else let var x = head xxs, var xs = tail
(if p(x) then x : filter(p, xs)
else filter(p,xs)) in ...
xxs in
fun map op xxs = if (xxs==[])then []
else (let var x = head xxs, var xs = tail xxs in
op(x) : map(op, xs))
Compreensão de Listas em
LF3

Notação
[exp qualificador,...,qualificador]
Onde
exp é uma expressão
qualificador é um gerador da forma for x in lista
O ultimo qualificador pode ser uma condição da
forma if exp
Compreensão de Listas em LF3

[x+1 for x in 3..1 ]
= [4, 3, 2]

[x+1 for x in 3..1 if x==1]
= [2]

[[x, y] for x in 0..2, for y in 3..5 if x + y == 5]
= [[0, 5], [1, 4], [2, 3]]

let fun id x = x in [ f(x) for x in 1..3, for f in [id]]
= [1, 2, 3]
Compreensão de Listas


Redefina as funções map e filter usando
compreensão
Defina quicksort usando compreensão;
primeiro para uma lista de números e depois
para listas de um tipo arbitrário, com uma
relação de ordem
Compreensão de Listas

quicksort em LF3
let fun quicksort op xs =
if (xs ==[]) then []
else (quicksort(op, [k for k in tail(xs) if op(k, head(xs))]))
^^ ([head(xs)] ^^
(quicksort(op, [y for y in tail(xs) if (not op(y, head(xs)))])))
in
let fun maiorQue x y = x > y in quicksort(maiorQue, [2,1,4,3])
Mais sobre Programação Funcional
Indução em Listas


Uma prova indutiva de
 xs  P(xs)
é estabelecida provando-se:
Caso []. P([])
Caso (x:xs) P(xs)  P(x:xs)
Exercício: provar associatividade de
concatenação de listas
• (xs ^^ ys) ^^ zs = xs ^^ (ys ^^ zs)
Leitura

Programming Language Concepts and
Paradigms
• Capítulo 2 (Seção 2.4)
• Capítulo 13

Introduction to Functional
Programming
• Capítulos 3 e 5