(actualizado em 22 de Fevereiro de 2019)
O paradigma de programação funcional, declarativo, conceptualmente limpo e com uma teoria matemática muito elegante e robusta (o denominado cálculo-$\lambda$), consiste em definir funções (sobre objectos básicos, iteráveis, ou mesmo outras funções) directamente, sem usar recorrências nem ciclos. Na programação funcional pura não há lugar para o mecanismo de atribuição no corpo das definições, ficando assim vedados os efeitos colaterais típicos da programação imperativa.
A programação funcional não é nativa da linguagem Python, que como sabemos é uma linguagem orientada a objectos.
Isso não invalida que se estude e utilize o paradigma de programação funcional em Python, bem pelo contrário,
apesar de várias das suas potencialidades não serem plenamente suportadas pela linguagem (ou suportadas apenas em extensões, como functools).
Em programação funcional, como o próprio nome indica, o conceito de função é primordial (vale a pena notar que em Python as funções são ainda assim objectos).
def f(x):
return x**2
type(f)
É muito pouco usual em matemática definir uma função sem lhe associar um nome (e uma regra de cálculo, claro). Em linguagens de programação, como Python, acontece algo semelhante. A função f definida acima é exemplo disso, tal como, todas as funções que definimos até agora (com uma honrosa excepção).
No entanto, é óbvio que uma função (como objecto matemático, ou como objecto em Python) é concebível sem ser necessário associar-lhe um nome.
Esta ideia, extremamente importante, foi sistematizada por Alonzo Church como o mecanismo de abstracção funcional do cálculo-$\lambda$, e é conhecida mais simplesmente por notação lambda (lambda é o nome da letra grega $\lambda$).
A linguagem Python suporta um fragmento (infelizmente demasiado simples) da notação lambda, em que a expressão de cálculo da função definida não pode ser composta nem conter comandos.
(lambda x:x**2)(5)
Se necessário podemos associar um nome a uma expressão lambda, o que produz um efeito equivalente à definição de funções mais usual.
g=(lambda x,y:x*y)
g(7,9)
Em programação funcional, as funções que definimos e com as quais podemos definir outras funções (por vezes ditas funções de ordem superior, por tomarem argumentos e/ou devolverem resultados que também são funções) são usualmente denominadas de combinadores.
O primeiro combinador disponibilizado pela linguagem Python que analisaremos, extremamente útil, permite aplicar uma mesma função a todos os elementos de uma lista (ou outro objecto iterável) obtendo-se um iterador contendo todos os resultados.
?map
Em geral, o resultado de map(f,[x1,x2,...,xn],[y1,y2,...,yn],...,[z1,z2,...,zn]) é (um iterador correspondente a) [f(x1,y1,...,z1),...,f(xn,yn,...,zn)].
A definição abaixo permite obter a lista dos quadrados dos valores de uma lista dada.
def quadrados(w):
return list(map(lambda x:x**2,w))
quadrados([5,6,7])
quadrados([5,6,7])
Suponhamos agora que queríamos saber, numa lista de números, quais são quadrados perfeitos.
% pylab inline
def qperfeitoQ(x):
return ceil(sqrt(x))**2==x
def qperfeitos(w):
return list(map(qperfeitoQ,w))
qperfeitos([1,7,0,9,0.3,25])
Como explicado acima, map pode ser utilizado com funções de vários argumentos, sendo-lhe nesse caso fornecidas várias listas. No exemplo que se segue usa-se map para implementar funcionalmente uma função que dada uma lista de valores [a0,a1,a2,...,an] calcula a lista das suas potências relativamente à posição, isto é, a cada elemento ai vai corresponder ai**i.
def exp(b,e):
return b**e
def powers(w):
return list(map(exp,w,range(len(w))))
powers([4,5,6,2,0,2])
Outros dois combinadores extremamente úteis (any e all) permitem verificar a existência (ou ausência) de valores lógicos em listas Booleanas.
Suponha-se que queríamos, dada uma lista de números, saber se existe algum quadrado perfeito.
def algumperfeito(w):
return any(list(map(qperfeitoQ,w)))
algumperfeito([3,3,3,5])
Imagine-se que pretendíamos, por outro lado, saber se todos os valores são quadrados perfeitos.
def todosperfeitos(w):
return all(list(map(qperfeitoQ,w)))
todosperfeitos([9,100,49])
Outro exemplo interessante, e simples, consiste na definição de uma função Booleana que determine se um dado valor ocorre, ou não, numa dada lista.
def pertenceQ(x,w):
def igualx(y):
return x==y
return any(list(map(igualx,w)))
pertenceQ(1,[3,2,1])
Outro combinador relacionado com any e all é filter, que permite omitir de uma lista (ou objecto iterável) os valores que não satisfaçam uma dada condição. Podemos usá-la, por exemplo, para contar quantos elementos de uma lista são quadrados perfeitos.
def quantosperfeitos(w):
return len(list(filter(qperfeitoQ,w)))
quantosperfeitos([8,100,49])
Vale a pena referir que estes combinadores são muitas vezes substituídos, em Python, por definições por compreensão.
Na verdade, é fácil de perceber que map(f,w) é equivalente a [f(x) for x in w].
Analogamente, any(w) é equivalente a [x for x in w if x]!=[].
Deixa-se como exercício encontrar as expressões que simulam o comportamento de all e filter.
É fácil, por exemplo, definir a função que calcula a transposta de uma matriz directamente usando definições por compreensão.
def transposta(m):
return [[m[i][j] for i in range(len(m))] for j in range(len(m[0]))]
transposta([[1,2,3],[4,5,6]])
Vale a pena notar aqui, de todo o modo, que apesar de as definições por compreensão serem bastante poderosas, sucintas, facilmente inteligíveis e simples de usar, elas podem ser em geral bem menos eficientes que a utilização dos correspondentes combinadores, como se ilustra de seguida.
from time import sleep
### a função f devolve o argumento com um delay de 0.5 segundos
def f(x):
sleep(0.5)
return x
%time any(map(lambda x:f(x)==0,range(100)))
%time any([f(x)==0 for x in range(100)])
Note-se que a diferença entre os dois casos consiste na utilização de map (que devolve um iterador que só será utilizado pelo combinador any para construir os valores necessários até ao aparecimento do primeiro True) versus a construção explícita de toda a lista por compreensão (que demora cerca de 50 segundos).
O primeiro combinador verdadeiramente importante disponibilizado pela linguagem Python permite aplicar sucessivamente uma função binária aos diversos elementos de uma lista (ou outro objecto iterável) acumulando o resultado.
from functools import reduce
?reduce
Em geral, o resultado de reduce(f,[x1,x2,...,xn],d) é f(...f(f(d,x1),x2)...,xn). Tipicamente o valor d corresponderá ao elemento neutro da operação dada por f.
Atente-se, num primeiro exemplo, na forma simples como podemos definir uma função que calcula o valor médio de uma lista dada.
soma=lambda x,y:x+y
def somalista(w):
return reduce(soma,w,0)
def media(w):
if len(w)==0:
print("erro, lista vazia")
else:
return somalista(w)/len(w)
media([3,6,12])
Podemos também calcular funcionalmente a função factorial, de forma em tudo semelhante à usada em somalista.
def factfun(n):
return reduce(lambda x,y:x*y,range(1,n+1),1)
factfun(0)
Facilmente se usa esta definição para obter uma função que calcula a lista dos factoriais dos valores de uma lista dada.
def factlist(w):
return list(map(factfun,w))
factlist(range(10))
Vale a pena notar que, neste contexto, o combinador map não é estritamente essencial, já que pode ser definido à custa de reduce.
def mymap(f,w):
return reduce(lambda r,x:r+[f(x)],w,[])
mymap(lambda x:x+1,[3,4,5])
Da mesma forma, os combinadores any e all são também definíveis usando reduce.
def myany(w):
return reduce(lambda x,y:x or y,w,False)
myany([False,False,False])
Deixa-se a definição correspondente a all como exercício.
Vale a pena notar que o combinador reduce é suficente para, funcionalmente, definirmos qualquer função que possa ser definida imperativamente com um ciclo, desde que possamos determinar à partida o número de vezes que é iterado. Equivalentemente, isto corresponde também ao poder das definições recursivas cuja profundidade esteja predeterminada.
O seguinte combinador, definido à custa de reduce, ilustra essa possibilidade.
def nest(f,n,x):
return reduce(lambda a,b:f(a),range(n),x)
Vale apena notar que nest(f,n,x) calcula f(...f(f(x))...) onde f é aplicada n vezes.
nest(lambda x:x+1,5,10)
Por exemplo, o valor mínimo de uma lista pode ser calculado facilmente percorrendo a lista.
def minimo(w):
def fora(u):
return u[1:] if u[0]>u[1] else [u[0]]+u[2:]
return nest(fora,len(w)-1,w)[0]
minimo([4,1,7,-10,5,3])
Há inúmeras situações em que nest (ou reduce) são úteis, mas não é possível com elas simular aquilo que se consegue definir imperativamente com ciclos ou recursões cuja profundidade máxima não seja determinável à partida.
Para tal é necessário dispôr de um combinador adicional fixedpoint tal que
fixedpoint(f,x) calcula sucessivamente x,f(x),f(f(x)),f(f(f(x))),... devolvendo (se existir) o primeiro valor y desta sequência que seja um ponto fixo de f, isto é, tal que f(y) é igual a y.
Infelizmente este combinador não está disponível em Python, mas é muito fácil implementá-lo, por exemplo imperativamente.
def fixedpoint(f,x):
while x!=f(x):
x=f(x)
return x
fixedpoint(lambda x:x+1 if x<5 else x,0)
Uma definição alternativa, mais eficiente (porquê?), seria a seguinte.
def fixedpoint(f,x):
found=False
while not(found):
y=f(x)
if y==x:
found=True
else:
x=y
return x
Atente-se por exemplo na seguinte implementação funcional do cálculo do fecho transitivo de uma relação, recorrendo a fixedpoint.
def fechotrans(R):
def fecho(S):
return S+[[a[0],b[1]] for a in S for b in R if a[1]==b[0] and [a[0],b[1]] not in S]
return fixedpoint(fecho,R)
fechotrans([[0,1],[1,2],[2,3],[3,4]])
O combinador fixedpoint é bastante poderoso. Nomeadamente, é fácil de ver que nest pode ser definido à sua custa, o que se deixa como exercício.
Currying (e uncurrying) são conceitos importantes na teoria da programação funcional, e úteis em geral, que devem o seu nome a Haskell Curry, ilustre cientista, cujo primeiro nome é também o de uma das mais importantes linguagens de programação funcional.
A questão é simples. Seja f uma função binária. Para calcular valores de f temos de avaliar f(a,b) para os valores de a e b desejados, que são assim fornecidos em simultâneo. Suponhamos no entanto que, por alguma razão, o valor a está disponível antes de b.
Na versão curryed de f é possível avaliar f(a), que devolve uma função g tal que g(b)=f(a,b).
Currying consiste portanto em transformar uma função de vários argumentos numa função que recebe o primeiro argumento e retorna uma função que recebe o segundo argumento e retorna outra função e assim sucessivamente, até ser devolvido o resultado desejado após ser fornecido o último argumento.
O mecanismo inverso, que agrupa de novo os argumentos da função dá pelo nome de uncurrying.
Claramente, nada impede que definamos funções já em formato curryed, o que por vezes tem as suas vantagens.
def mymult(x):
def multx(y):
return x*y
return multx
dobro = mymult(2)
triplo = mymult(3)
mymult(7)(8),dobro(10)+triplo(5)
É possível fazer currying e uncurrying automaticamente, tirando partido da primitiva funcional partial, e da manipulação de sequências de argumentos (*args).
from functools import partial
def curryfun(f,n):
def curryult(h,i):
def newh(*args):
return partial(h,*args)
return newh
return reduce(curryult,range(n-1),f)
def somatres(x,y,z):
return x+y+z
somatrescurryed=curryfun(somatres,3)
somatrescurryed(5)(6)(7)
A operação de uncurrying é mais simples de implementar.
def aplica(f,x):
return f(x)
def uncurryfun(f):
def g(*args):
return reduce(aplica,args,f)
return g
somatresuncurryed=uncurryfun(somatrescurryed)
somatresuncurryed(5,6,7)
É útil e muitas vezes mesmo adequado programar usando os vários paradigmas de programação, sempre que o ambiente de programação os suporte, como é o caso do Python. Diferentes problemas têm muitas vezes soluções mais naturais em paradigmas distintos, embora isto seja algo que também depende do treino específico, intuição e gosto de cada um.
Vale a pena, no entanto, ter consciência da eficiência relativa das diferentes abordagens. Em primeiro lugar, usar primitivas nativas do ambiente em que programamos é, em princípio, sempre mais eficiente. Depois, em geral, a programação recursiva é tipicamente a pior opção, mesmo em ambientes de programação que disponham de mecanismos optimizados para iteração (que não é o caso do Python, por opção dos seus criadores).
Comparemos as seguintes definições alternativas do cálculo do factorial.
def factorial_rec(n):
if n==0:
return 1
else:
return n*factorial_rec(n-1)
def factorial_iter(n):
def factorial_iter_aux(n,r):
if n==0:
return r
else:
return factorial_iter_aux(n-1,n*r)
return factorial_iter_aux(n,1)
def factorial_imp_while(n):
r=1
while n>1:
r*=n
n+=-1
return r
def factorial_imp_for(n):
r=1
for i in range(n):
r*=(i+1)
return r
def factorial_func(n):
return reduce(lambda x,y:x*y,range(1,n+1),1)
from math import factorial
Para efeitos da comparação, vamos usar listas de valores aleatórios e aplicar cada uma das definições a todos eles. Para já vamos construir uma lista de 1000 valores entre 200 e 250.
from random import *
wsmall=[randrange(200,250) for i in range(1000)]
%time x=[factorial_rec(x) for x in wsmall]
%time x=[factorial_iter(x) for x in wsmall]
%time x=[factorial_imp_while(x) for x in wsmall]
%time x=[factorial_imp_for(x) for x in wsmall]
%time x=[factorial_func(x) for x in wsmall]
%time x=[factorial(x) for x in wsmall]
Tome-se agora uma lista de 100 valores aleatórios entre 1900 e 2000.
wmedium=[randrange(1900,2000) for i in range(100)]
%time x=[factorial_rec(x) for x in wmedium]
import sys
sys.setrecursionlimit(2100)
%time x=[factorial_rec(x) for x in wmedium]
%time x=[factorial_iter(x) for x in wmedium]
%time x=[factorial_imp_while(x) for x in wmedium]
%time x=[factorial_imp_for(x) for x in wmedium]
%time x=[factorial_func(x) for x in wmedium]
%time x=[factorial(x) for x in wmedium]
Finalmente, tome-se uma lista com apenas 10 valores aleatórios mas entre 40000 e 50000, deixando desde já para trás as versões recursivas, que claramente excederão o limite de recursão imposto.
wlarge=[randrange(40000,50000) for i in range(10)]
%time x=[factorial_imp_while(x) for x in wlarge]
%time x=[factorial_imp_for(x) for x in wlarge]
%time x=[factorial_func(x) for x in wlarge]
%time x=[factorial(x) for x in wlarge]
As conclusões são simples de retirar, já que as várias versões foram apresentadas por ordem crescente de eficiência.
Neste ponto é útil notar que os paradigmas de programação recursivo, imperativo e funcional, embora tão distintos, têm exactamente o mesmo poder expressivo. O mesmo é dizer que qualquer algoritmo implementado num dos paradigmas pode também ser implementado noutro. Não faremos uma demonstração exaustiva deste facto, mas ilustramos abaixo as razões subjacentes a este facto.
Já vimos antes que uma definição recursiva pode ser transformada numa definição imperativa usando uma pilha de chamadas. Aqui, veremos como transformar, sistematicamente, definições recursivas em definições puramente funcionais.
A título de exemplo usamos a definição recursiva da função factorial.
def factorial_rec(n):
if n==0:
return 1
else:
return n*factorial_rec(n-1)
O seguinte combinador, denominado por Y ou também por combinador paradoxal, (é uma versão do combinador que) foi proposto para este fim por Alan Turing, talvez o mais importante e conhecido pioneiro da ciência da computação. O combinador é um determinador de pontos fixos para definições de funções, e permite eliminar a recursão, como se exemplifica.
def Y(h):
def W(f):
def r(x):
return h(f(f))(x)
return r
return W(W)
def FACT(f):
def fact(n):
if n==0:
return 1
else:
return n*f(n-1)
return fact
Y(FACT)(5)
Tome-se agora outro exemplo: uma função que replica várias vezes cada elemento de uma lista dada.
def replica(w,n):
if w==[]:
return []
else:
return [w[0] for i in range(n)]+replica(w[1:],n)
replica([5,6,7],3)
def REP(f):
def rep(w,n):
if w==[]:
return []
else:
return [w[0] for i in range(n)]+f(w[1:],n)
return rep
Y(REP)([5,6,7],3)
À primeira vista poderia parecer que o combinador Y não é, afinal, tão espectacular como isso. No entanto, o único problema é que na teoria da programação funcional todas as funções recebem sempre um argumento de cada vez. Assim, precisamos de trabalhar com uma versão curryed da definição, em vez da função binária.
def REP(f):
def rep(w,n):
if w==[]:
return []
else:
return [w[0] for i in range(n)]+uncurryfun(f)(w[1:],n)
return curryfun(rep,2)
Y(REP)([5,6,7])(3)
Para transformar qualquer definição funcional numa definição imperativa equivalente, basta notar que os combinadores fundamentais têm definições imperativas, e aplicar a ideia sistematicamente.
def map_imperativo(f,iterable):
for x in iterable:
yield f(x)
list(map_imperativo(lambda x:x+1,[3,4,5]))
Voltaremos a falar, com mais cuidado de yield. A construção é ainda assim simples de compreender. Optámos por esta definição, em vez de uma definição mais óbvia usando apenas listas, por map devolver um iterável.
def reduce_imperativo(f,iterable,x):
r=x
for y in iterable:
r=f(r,y)
return r
reduce_imperativo(lambda x,y:x+y,[3,4,5],0)
Também as definições por compreensão podem facilmente ser implementadas imperativamente.
def compreens_imperativo(expr,iterable,cond):
for i in iterable:
if cond(i):
yield expr(i)
list(i**2 for i in range(10) if i%2==0)
list(compreens_imperativo(lambda i:i**2,range(10),lambda i:i%2==0))
Vale a pena recordar que a definição de fixedpoint já é imperativa, tal como foi dada.
A tradução de programas imperativos em recursivos é relativamente imediata se entendermos cada iteração de um ciclo, while ou for, como a aplicação de uma função que transforma o estado corrente (entendido como o valor associado a todos os nomes relevantes para o programa).
Nessa perspectiva, cada ciclo
while cond:
prog
pode ser simulado como se segue, associando funções adequadas à condição cond e ao corpo do ciclo prog.
def enquanto(cond,prog,estado):
if cond(estado):
return enquanto(cond,prog,prog(estado))
else:
return estado
Para exemplificar, tome a seguinte definição imperativa.
def factorial_imp_while(n):
r=1
while n>1:
r*=n
n+=-1
return r
Os nomes relevantes no contexto deste programa são: n e r. O estado será então um dicionário contendo os dois valores, associados às chaves "n" e "r". O estado inicial corresponderá a {"n":n,"r":1}, já que r é inicializado antes do ciclo se iniciar.
A condição na guarda do ciclo n>1, é avaliada em cada estado verificando se a sua primeira componente é maior do que 1, o que corresponde a estado["n"]>1. Finalmente, o corpo do programa actualiza o estado da forma indicada no corpo do ciclo, o que corresponde a executar estado["r"]*=estado["n"] e estado["n"]+=-1.
Temos, então, o seguinte programa recursivo equivalente.
def factrec(n):
def cond(estado):
return estado["n"]>1
def passo(estado):
estado["r"]*=estado["n"]
estado["n"]+=-1
return estado
return enquanto(cond,passo,{"n":n,"r":1})["r"]
factrec(5)
Analogamente, cada ciclo
for i in iterable:
prog
pode ser simulado como se segue, associando uma função adequada ao corpo do ciclo prog.
def para(iterable,prog,estado):
iterador=iter(iterable)
go=True
while go:
i=next(iterador,None)
if i!=None:
estado=prog(i,estado)
else:
go=False
return estado
Tome-se um exemplo simples.
a=0
for i in [3,4,5]:
a=a+i
print(a)
def prog(i,estado):
estado["a"]=estado["a"]+i
print(estado["a"])
return estado
para([3,4,5],prog,{"a":0});
itertools, que exploraremos mais adiante. Introdução à Programação em Mathematica (3a edição): J. Carmo, A. Sernadas, C. Sernadas, F. M. Dionísio, C. Caleiro, IST Press, 2014.
Think Python: How to think like a computer scientist: A. Downey, Green Tea Press, 2012.
Introduction to Computation and Programming Using Python (revised and expanded edition): J. V. Guttag, MIT Press, 2013.
The Art of Computer Programming: D. E. Knuth, Addison-Wesley (volumes 1--3, 4A), 1998.
Learning Python (fifth edition): M. Lutz, O'Reilly Media, 2013.
Programação em Python: Introdução à programação utilizando múltiplos paradigmas: J. P. Martins, IST Press, 2015.
Introdução à Programação em MatLab: J. Ramos, A. Sernadas e P. Mateus, DMIST, 2005.
Learning IPython for Interactive Computing and Data Visualization: C. Rossant, Packt Publishing, 2013.
Programação em Mathematica: A. Sernadas, C. Sernadas e J. Ramos, DMIST, 2003.