Upload
internet
View
104
Download
0
Embed Size (px)
Citation preview
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 LF2O 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 T2f: (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 LF2O 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 LF2Funçõ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 LF2Funçõ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
minfun 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 + 1Pred 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çãoexp(x, 0) = 1 (1)exp(x, n+1) = x * exp(x, n) (2)
Provar:exp(x, m+n) = exp(x, m) * exp(x, n)Caso (0). Caso (n+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• [] • [1,2,3]• [[1,2],[3]]• [suc, pred]• 1..5
Qual o tipo das listas acima
: [T] : [int]
: [[int]]
: [int int] : [int]
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 head(x : xs) = x tail(x : xs) = xs Concatenação [] ^^ 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 aelse (let var x = head xxs, var xs = tail xxs in
op(x, fold(op,a, xs))) 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 xxs in
(if p(x) then x : filter(p, xs)
else filter(p,xs)) 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 FuncionalInduçã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