Funções Curried
Vamos introduzir uma nova notação para definir funções de
ordem superior.
Suponhamos que temos uma função f que está definida como
sendo do tipo int  (int  int), desta forma faz sentido escrever
f 5 (uma aplicação de f a 5) que denota uma função do tipo
int  int.
A aplicação desta função a 3 continua a fazer sentido e escrevese (f 5) 3.
Aqui temos um exemplo em que a função é representada por
uma expressão composta em vez de um nome.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
49
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções Curried
Como esta notação irá ocorrer muito frequentemente quando
trabalhamos com funções de ordem superior, vamos assumir
associatividade à esquerda na aplicação de funções e eliminar os
parêntesis.
Assim f 5 3 é lido com (f 5) 3 e em geral
E1 E2 ... En é lido como ( ... (E1 E2) E3 ...) En)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
50
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções Curried
Com base nesta convenção introduz-se uma notação mais
simples para definir funções como f - a notação curried.
Assim nas definições
fun soma m n = m + n
fun vezes m n = m * n
só a sintaxe das funções mudou, a semântica é a mesma.
Por exemplo soma é uma função que tem como argumento um
inteiro m e tem como resultado uma função, a qual tem como
argumento um inteiro n e cujo resultado é m + n.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
51
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções Curried
Embora possa parecer que esta notação é apenas mais uma
forma de escrever somas e multiplicações, na verdade temos
mais do que isso.
Podemos escrever expressões ‘intermédias’ tais como vezes 3
que representa a função que multiplica os seus argumentos por 3.
Esta expressão pode depois ser usada em qualquer contexto
onde faça sentido. Por exemplo
val triplo = vezes 3
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
52
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções Curried
No exemplo anterior temos a definição de uma função
(triplo: int  int) que não faz uso de parâmetros.
No entanto, da definição de triplo e vezes temos que
para qualquer argumento inteiro x:
triplo x = vezes 3 x = 3 * x
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
53
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções Curried
Também podemos escrever expressões do tipo
val funnyfun = dobro ° (soma 6)
que descreve uma função do tipo int  int e é a composição de
uma função que adiciona 6 ao seu argumento e uma função que
duplica o respectivo argumento.
funnyfun 10 = dobro (soma 6 10) = dobro (6+10) = dobro 16 = 2*16 = 32
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
54
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções Curried
De uma forma geral, para qualquer função da forma
fun f (a1, a2, ..., an) = b
f: (1 x 2 x ... x n)  
a1: 1, a2: 2, ..., an: n, b: 
É possível definir a sua versão curried:
fun curryf a1, a2, ..., an = b
curryf: 1  (2  (...  (n  ) ... ))
Assume-se associatividade à direita para o operador . Assim
podemos abreviar:
curryf: 1  2  ...  n  
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
55
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Listas
Um conceito bastante importante em matemática é o de
sequência ou lista de elementos.
As listas também desempenham um papel preponderante na
programação funcional, por isso vamos estudar as listas e
operações sobre estas.
A importância das listas advém do facto de estas providenciarem
uma forma simples de agrupar elementos.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
56
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Listas
Podemos ver uma lista como um valor que consiste num número
arbitrário e finito de elementos, todos do mesmo tipo.
Se T é o tipo dos elementos da lista então escrevemos T list para
representar o novo tipo.
Assim, o novo operador sobre tipos - list - estende o nosso
sistema de tipos, o que nos permite usar tipos tais como:
int list
(bool x string) list
(int list) list
(int  string) list
int  (string list)
 list
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
(lista de inteiros)
(lista de pares booleanos-inteiros)
(lista de listas de inteiros)
(lista de funções de inteiros para strings)
(funções de inteiros para lista de strings)
(lista de elementos do tipo )
57
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Listas
Iremos frequentemente escrever listas usando a seguinte
notação:
[5, 6, 3, 2, 8]
[true, true, false]
(um valor do tipo int list)
(um valor do tipo bool list)
Uma expressão da forma [not false, 3<5, 3 = 5] descreve um valor
que é uma lista (bool list, neste caso) e este valor pode também
ser representado pela sua forma simplificada [true, true, false].
Note-se que não são permitidas listas com elementos de tipos
distintos, como por exemplo:
[3, true, 5, 8]
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
58
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Listas
A lista vazia (com zero elementos) é escrita simplesmente com [],
que se pronuncia ‘nil’ e temos que o seu tipo é:
[]:  list
uma vez que [] denota, polimorficamente, uma lista vazia de
qualquer tipo de elementos.
O extremo esquerdo da lista é visto como o início da lista e usa-se
um operador infixo especial (denotado por :: e que se lê cons)
para adicionar um novo elemento ao início da lista.
Por exemplo:
5::[6, 3, 2, 8] = [5, 6, 3, 2, 8]
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
59
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Listas
O tipo do operador :: é dado por  x  list   list
o que nos garante que apenas podemos adicionar um elemento à
lista se este for do mesmo tipo que os elementos já existentes.
Os construtores de listas, são pois o operador constante [] e o
operador ::. De facto qualquer lista que tenhamos pode ser
construída inteiramente através do uso de [] e de ::.
Assim a notação anterior que usamos para listas é uma
abreviatura da notação canónica (notação que recorre apenas às
operações construtoras das listas), sendo que as seguintes listas
são equivalentes:
[1, 2, 3, 4]
1::2::3::4::[]
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
60
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Operações sobre listas
Além dos construtores referidos atrás, podemos considerar
algumas operações acessórias, que iremos introduzir através de
exemplos:
@: ( list x  list)   list, operador infixo de concatenação
de listas
[1, 2, 3] @ [4, 5] = [1, 2, 3, 4, 5]
rev:  list   list, função que inverte listas
rev [1, 2, 3, 4, 5] = [5, 4, 3, 2, 1]
null:  list  bool, função que indica se uma lista é a lista
vazia
implode: string list  string, função que concatena as
strings que constam de uma lista de strings
implode [“isto ”, “ e”, “ aquilo”] = “isto e aquilo”
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
61
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Operações sobre listas
link: ( list) list   list, função que concatena as listas que
constam de uma lista de listas
link [[1, 2], [3, 4], [5, 6]] = [1, 2, 3, 4, 5, 6]
length:  list  int, função que dá o comprimento de uma
lista
length [2, 4, 6, 9] = 4
hd:  list  , função que dá o elemento à cabeça da lista
hd [1, 5, 8, 3] = 1
tl:  list   list, função que dá a cauda da lista
tl [1, 5, 8, 3] = [5, 8, 3]
member: = list  =  bool, função que testa se um dado
elemento pertençe à lista
member [3, 6, 2, 5, 2, 7] 5 = true
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
62
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Operações sobre listas
upto: (int x int)  int list, operador infixo que constrói a lista
dos inteiros entre dois dados valores
1 upto 5 = [1, 2, 3, 4, 5]
copy: int     list, função que constrói uma lista com n
cópias de um dado valor
copy 6 10 = [10, 10, 10, 10, 10, 10]
sumlist: int list  int, função que retorna a soma dos inteiros
da lista
sumlist [1, 6, 2, 7, 9] = 1 + 6 + 2 + 7 + 9 = 25
prodlist: int list  int, função que retorna o produto dos
inteiros da lista
prodlist [2, 6, 1, 4] = 2 * 6 * 1 * 4 = 48
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
63
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Pattern matching com listas
Uma vez que todas as listas são ou [] ou da forma a::x, podemos
definir funções sobre listas, descrevendo qual o seu
comportamento em cada um dos casos do argumento.
Muitas funções podem ser introduzidas utilizando apenas dois
casos: aquele em que se trata da lista vazia (utilizamos como
parâmetro o construtor []) e o outro em que temos uma lista com
um ou mais elementos (utilizamos como parâmetro o construtor ::
e variáveis para representarem a cabeça e a cauda da lista: a::x).
Podemos também ter funções sobre listas que necessitem de ser
definidas utilizando mais do que dois casos.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
64
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Pattern matching com listas
Por exemplo, a função alternate:  list   list retorna a lista
composta por ‘elemento não, elemento sim’ da lista recebida como
argumento. A sua definição inclui casos separados para a lista
vazia, para a lista com um único elemento e para listas com dois
ou mais elementos:
fun alternate(a::b::x) = b :: alternate x
| alternate [a] = []
| alternate [] = []
o primeiro caso irá emparelhar com listas que tenham 2 ou mais
elementos, sendo que a será ligado ao 1º elemento, b ao 2º e x à
cauda da lista. O segundo caso apenas irá emparelhar com listas
que tenham um único elemento e o terceiro com listas vazias.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
65
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Pattern matching com listas
Temos assim a definição das funções acima apresentadas,
utilizando o ‘pattern matching’:
fun rev [] = []
fun implode [] = “”
| rev (a::x) = (rev x) @ [a]
| implode (a::x) = a ^ implode x
fun link [] = []
| link (a::x) = a @ link x
fun length [] = 0
| length (a::x) = 1 + length x
fun hd [] = error “hd de []”
| hd (a::x) = a
fun tl [] = error “tl de []”
| tl (a::x) = x
fun member a [] = false
| member a (b::x) = if a=b then true else member a x
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
66
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Pattern matching com listas
fun null (a::x) = false
| null [] = true
fun sumlist (a::x) = a + sumlist x
| sumlist [] = 0
fun prodlist (a::x) = a * prodlist x
| prodlist [] = 1
fun (a::x) @ y = a::(x @ y)
| [] @ y = y
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
67
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções de ordem superior com listas
As funções de ordem superior que são apresentadas de seguida
têm um maior grau de generalidade e podem servir de base a uma
redefinição mais simples de algumas operações já apresentadas.
Além disso, permitem encapsular o processamento recursivo das
listas.
A função map aplica uma função f a todos os elementos de uma
lista e retorna a lista das imagens por f desses elementos.
A função filter aplica um predicado p aos elementos de uma lista e
retorna a lista dos elementos que satisfazem p.
A função exists aplica um predicado p aos elementos de uma lista e
retorna true se existe algum elemento que satisfaça p e false caso
contrário.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
68
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções de ordem superior com listas
A função all aplica um predicado p aos elementos de uma lista e
retorna true se todos os elementos satisfazem p e false caso
contrário.
A função zip aplica uma função binária e curried f a duas listas,
elemento a elemento, e retorna como resultado a lista das imagens
por f desses elementos.
As funções accumulate e reduce:
accumulate f a [a1, a2, a3, ..., an] = f (... f (f (f a a1) a2) a3 ...) an
reduce f a [a1, a2, a3, ..., an] = f a1 (f a2 (f a3 ( ... (f an a) ...)))
Assim, accumulate calcula em primeiro lugar f a a1 e depois este
valor e a2 entram como argumento para a invocação seguinte, etc.
A função reduce aplica f aos seus argumentos pela ordem inversa.
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
69
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções de ordem superior com listas
fun map f [] = []
| map f (a::x) = f a :: map f x
(  )   list   list
fun filter p [] = []
| filter p (a::x) = if p a then a :: filter p x
else filter p x
(  bool)   list   list
val doublelist = map (times 2)
fun exists p [] = false
| exists p (a::x) = if p a then true
else exists p x
fun all p [] = true
| all p (a::x) = if p a then all p x
else false
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
70
val onlyeven = filter even
(  bool)   list  bool
val anyeven = exists even
(  bool)   list  bool
val alleven = all even
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)
Funções de ordem superior com listas
fun zip f [] [] = []
| zip f (a::x) (b::y)= f a b :: zip f x y
(    )   list   list   list
| zip f x y error “listas com tamanhos diferentes”
fun accumulate f a [] = a
(    )     list  
| accumulate f a (b::x) = accumulate f (f a b) x
fun reduce f a [] = a
| reduce f a (b::x) = f b (reduce f a x)
Universidade da Madeira
Departamento de Matemática e Engenharias
Elsa Carvalho
71
(    )     list  
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2005/06)