Qual é o equivalente 'pythônico' à função 'dobrar' da programação funcional?

117

Qual é a maneira mais idiomática de conseguir algo como o seguinte, em Haskell:

foldl (+) 0 [1,2,3,4,5]
--> 15

Ou seu equivalente em Ruby:

[1,2,3,4,5].inject(0) {|m,x| m + x}
#> 15

Obviamente, Python fornece a reducefunção, que é uma implementação de fold, exatamente como acima, no entanto, fui informado que a maneira 'pítônica' de programação era evitar lambdatermos e funções de ordem superior, preferindo compreensões de lista quando possível. Portanto, há uma maneira preferida de dobrar uma lista, ou estrutura semelhante a uma lista em Python que não seja a reducefunção, ou é reducea maneira idiomática de fazer isso?

mistertim
fonte
2
sumnão é bom o suficiente?
JBernardo
3
não tenho certeza se este é um bom exemplo para sua pergunta. Isso pode ser facilmente alcançado com o sum, você pode fornecer alguns tipos diferentes de exemplos.
Jamylak
14
Ei JBernardo - A soma de uma lista de números era um exemplo bastante degenerado, estou mais interessado na ideia geral de acumular os elementos de uma lista usando alguma operação binária e um valor inicial, não somando números inteiros especificamente.
mistertim
1
@mistertim: sum()na verdade, fornece funcionalidade limitada com isso. sum([[a], [b, c, d], [e, f]], [])retorna [a, b, c, d, e, f]por exemplo.
Joel Cornett
Embora o caso de fazer isso com listas seja uma boa demonstração de coisas a serem observadas com essa técnica - +em listas é uma operação de tempo linear tanto no tempo quanto na memória, tornando toda a chamada quadrática. O uso list(itertools.chain.from_iterable([a], [b,c,d],[e,f],[]])é linear no geral - e se você só precisar iterar sobre ele uma vez, pode cancelar a chamada para listpara torná-lo constante em termos de memória.
lvc

Respostas:

116

A maneira pitônica de somar uma matriz está usando sum. Para outros fins, às vezes você pode usar alguma combinação de reduce(do functoolsmódulo) e o operatormódulo, por exemplo:

def product(xs):
    return reduce(operator.mul, xs, 1)

Esteja ciente de que reduceé realmente um foldl, em termos de Haskell. Não há sintaxe especial para realizar dobras, não há builtin foldre, na verdade, usar reducecom operadores não associativos é considerado um estilo incorreto.

Usar funções de ordem superior é bastante pitônico; faz bom uso do princípio do Python de que tudo é um objeto, incluindo funções e classes. Você está certo ao dizer que lambdas são desaprovados por alguns Pythonistas, mas principalmente porque eles tendem a não ser muito legíveis quando se tornam complexos.

Fred Foo
fonte
4
@JBernardo: você está dizendo que qualquer coisa que não esteja no módulo embutido não é pítônico?
Fred Foo
4
Não, isso seria estúpido de dizer. Mas me dê uma única razão por que você acha que o GvR odiaria tanto a função de redução no ponto de removê-la de builtins?
JBernardo
6
@JBernardo: porque as pessoas tentam fazer truques muito espertos com ele. Para citar aquele post do blog, "a aplicabilidade de reduce()é praticamente limitada a operadores associativos e, em todos os outros casos, é melhor escrever o loop de acumulação explicitamente." Portanto, seu uso é limitado, mas mesmo GvR aparentemente teve que admitir que é útil o suficiente para mantê-lo na biblioteca padrão.
Fred Foo
13
@JBernardo, isso significa que todo uso de fold em Haskell e Scheme é igualmente ruim? É apenas um estilo diferente de programação, ignorá-lo e colocar os dedos nos ouvidos e dizer que não está claro não significa que seja. Como a maioria das coisas que têm um estilo diferente, é preciso prática para se acostumar com isso . A ideia é colocar as coisas em categorias gerais para que seja mais fácil raciocinar sobre os programas. "Oh, eu quero fazer isso, hmm, parece uma dobra" (ou um mapa, ou uma planificação, ou uma planificação e uma dobra sobre isso)
Wes
3
Lambda em Python não pode conter mais de uma expressão. Você não pode tornar isso complexo, mesmo se tentar muito. Portanto, os Pythonistas que não gostam deles provavelmente não estão acostumados e, portanto, não gostam do estilo de programação funcional.
golem
16

Haskell

foldl (+) 0 [1,2,3,4,5]

Pitão

reduce(lambda a,b: a+b, [1,2,3,4,5], 0)

Obviamente, esse é um exemplo trivial para ilustrar um ponto. Em Python, você apenas faria sum([1,2,3,4,5])e até mesmo os puristas de Haskell geralmente prefeririam sum [1,2,3,4,5].

Para cenários não triviais quando não há função de conveniência óbvia, a abordagem idiomática pythônica é escrever explicitamente o loop for e usar a atribuição de variável mutável em vez de usar reduceou a fold.

Esse não é o estilo funcional, mas é a forma "pítônica". Python não foi projetado para puristas funcionais. Veja como o Python favorece as exceções para controle de fluxo para ver como o python idiomático não é funcional.

argila
fonte
12
as dobras são úteis para mais do que "puristas" funcionais. Eles são abstrações de propósito geral. Problemas recursivos são generalizados na computação. As dobras oferecem uma maneira de remover o clichê e uma maneira de tornar seguras as soluções recursivas em linguagens que não oferecem suporte nativo à recursão. Então, uma coisa muito prática. Os preconceitos da GvR nesta área são lamentáveis.
itsbruce
12

No Python 3, o reducefoi removido: Notas de lançamento . No entanto, você pode usar o módulo functools

import operator, functools
def product(xs):
    return functools.reduce(operator.mul, xs, 1)

Por outro lado, a documentação expressa preferência por for-loop em vez de reduce, portanto:

def product(xs):
    result = 1
    for i in xs:
        result *= i
    return result
Kyr
fonte
8
reducenão foi removido da biblioteca padrão do Python 3. reducemovido para o functoolsmódulo conforme você mostra.
argila
@clay, acabei de pegar a frase das notas de lançamento do Guido, mas você pode estar certo :)
Kyr
6

A partir Python 3.8, e a introdução de expressões de atribuição (PEP 572) ( :=operador), que dá a possibilidade de nomear o resultado de uma expressão, podemos usar uma compreensão de lista para replicar o que outras línguas chamam de operações dobrar / dobrar / reduzir:

Dada uma lista, uma função redutora e um acumulador:

items = [1, 2, 3, 4, 5]
f = lambda acc, x: acc * x
accumulator = 1

podemos dobrar itemscom a ffim de obter o resultado accumulation:

[accumulator := f(accumulator, x) for x in items]
# accumulator = 120

ou em forma condensada:

acc = 1; [acc := acc * x for x in [1, 2, 3, 4, 5]]
# acc = 120

Observe que, na verdade, essa também é uma operação "scanleft", pois o resultado da compreensão da lista representa o estado da acumulação em cada etapa:

acc = 1
scanned = [acc := acc * x for x in [1, 2, 3, 4, 5]]
# scanned = [1, 2, 6, 24, 120]
# acc = 120
Xavier Guihot
fonte
5

Você também pode reinventar a roda:

def fold(f, l, a):
    """
    f: the function to apply
    l: the list to fold
    a: the accumulator, who is also the 'zero' on the first call
    """ 
    return a if(len(l) == 0) else fold(f, l[1:], f(a, l[0]))

print "Sum:", fold(lambda x, y : x+y, [1,2,3,4,5], 0)

print "Any:", fold(lambda x, y : x or y, [False, True, False], False)

print "All:", fold(lambda x, y : x and y, [False, True, False], True)

# Prove that result can be of a different type of the list's elements
print "Count(x==True):", 
print fold(lambda x, y : x+1 if(y) else x, [False, True, True], 0)
Frédéric
fonte
Você troca os argumentos ao fredor no seu caso recursivo.
KayEss de
7
Como o Python não tem recursão de cauda, ​​isso vai quebrar em listas mais longas e é um desperdício. Além disso, esta não é verdadeiramente a função "dobrar", mas apenas uma dobra esquerda, ou seja, dobrar, isto é, exatamente o que reducejá oferece (observe que a assinatura da função de redução é reduce(function, sequence[, initial]) -> value- também inclui a funcionalidade de dar um valor inicial para o acumulador).
cemper93 de
5

Não é realmente uma resposta à pergunta, mas uma linha para foldl e foldr:

a = [8,3,4]

## Foldl
reduce(lambda x,y: x**y, a)
#68719476736

## Foldr
reduce(lambda x,y: y**x, a[::-1])
#14134776518227074636666380005943348126619871175004951664972849610340958208L
Mehdi Nellen
fonte
2
Penso que esta é a melhor maneira de escrever o seu foldr: reduce(lambda y, x: x**y, reversed(a)). Agora ele tem um uso mais natural, funciona com iteradores e consome menos memória.
Mateen Ulhaq de
2

A resposta real para este problema (de redução) é: Basta usar um loop!

initial_value = 0
for x in the_list:
    initial_value += x #or any function.

Isso será mais rápido do que reduzir e coisas como PyPy podem otimizar loops como esse.

BTW, o caso da soma deve ser resolvido com a sumfunção

JBernardo
fonte
5
Isso não seria considerado pitônico para um exemplo como este.
Jamylak
7
Os loops Python são notoriamente lentos. Usar (ou abusar) reduceé uma maneira comum de otimizar um programa Python.
Fred Foo
2
@larsmans Por favor, não diga que reduzir é mais rápido que um simples loop ... Sempre haverá uma sobrecarga de chamada de função para cada iteração. Além disso, novamente, Pypy pode otimizar loops para a velocidade C
JBernardo
1
@JBernardo: sim, é isso que estou afirmando. Acabei de traçar o perfil de minha versão de productum em seu estilo, e é mais rápido (embora marginalmente).
Fred Foo
1
@JBernardo Assumindo uma função embutida (como operator.add) como argumento para reduzir: Essa chamada extra é uma chamada C (que é muito mais barata do que uma chamada Python) e economiza o despacho e a interpretação de algumas instruções de bytecode, que podem facilmente causar dezenas de chamadas de função.
1

Eu acredito que alguns dos respondentes desta questão perderam a implicação mais ampla da foldfunção como uma ferramenta abstrata. Sim, sumpode fazer a mesma coisa com uma lista de inteiros, mas este é um caso trivial. foldé mais genérico. É útil quando você tem uma sequência de estruturas de dados de formas variadas e deseja expressar claramente uma agregação. Então, em vez de ter que construir um forloop com uma variável agregada e recalcular manualmente a cada vez, uma foldfunção (ou a versão Python, que reduceparece corresponder a) permite que o programador expresse a intenção da agregação muito mais claramente, simplesmente fornecendo duas coisas:

  • Um valor inicial ou "semente" padrão para a agregação.
  • Uma função que obtém o valor atual da agregação (começando com a "semente") e o próximo elemento na lista e retorna o próximo valor de agregação.
rq_
fonte
Oi rq_! Eu acho que sua resposta seria melhorada e acrescentada muito se você folddesse um exemplo não trivial de que é difícil fazer de forma limpa em Python, e então " fold" isso em Python :-)
Scott Skiles
0

Posso estar um pouco atrasado para a festa, mas podemos criar um costume foldrusando cálculo lambda simples e função curry. Aqui está minha implementação de foldr em python.

def foldr(func):
    def accumulator(acc):
        def listFunc(l):
            if l:
                x = l[0]
                xs = l[1:]
                return func(x)(foldr(func)(acc)(xs))
            else:
                return acc
        return listFunc
    return accumulator  


def curried_add(x):
    def inner(y):
        return x + y
    return inner

def curried_mult(x):
    def inner(y):
        return x * y
    return inner

print foldr(curried_add)(0)(range(1, 6))
print foldr(curried_mult)(1)(range(1, 6))

Mesmo que a implementação seja recursiva (pode ser lenta), ela irá imprimir os valores 15e 120respectivamente

Calça
fonte