¿Cuál es el equivalente 'pitónico' a la función 'plegar' de la programación funcional?

116

¿Cuál es la forma más idiomática de lograr algo como lo siguiente, en Haskell:

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

O su equivalente en Ruby:

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

Obviamente, Python proporciona la reducefunción, que es una implementación de fold, exactamente como arriba, sin embargo, me dijeron que la forma 'pitónica' de programar era evitar lambdatérminos y funciones de orden superior, prefiriendo listas por comprensión cuando fuera posible. Por lo tanto, ¿hay una forma preferida de plegar una lista o una estructura similar a una lista en Python que no sea la reducefunción, o es reducela forma idiomática de lograr esto?

mistertim
fuente
2
sumno es lo suficientemente bueno?
JBernardo
3
No estoy seguro si este es un buen ejemplo para su pregunta. Se puede lograr fácilmente con sum, es posible que desee proporcionar algunos tipos diferentes de ejemplos.
jamylak
14
Hola JBernardo: resumir una lista de números fue un ejemplo bastante degenerado, estoy más interesado en la idea general de acumular los elementos de una lista usando alguna operación binaria y un valor inicial, no sumar enteros específicamente.
mistertim
1
@mistertim: en sum()realidad, proporciona una funcionalidad limitada con esto. sum([[a], [b, c, d], [e, f]], [])devuelve, [a, b, c, d, e, f]por ejemplo.
Joel Cornett
Aunque el caso de hacerlo con listas es una buena demostración de cosas a tener en cuenta con esta técnica, +en las listas es una operación de tiempo lineal tanto en tiempo como en memoria, lo que hace que toda la llamada sea cuadrática. El uso list(itertools.chain.from_iterable([a], [b,c,d],[e,f],[]])es lineal en general, y si solo necesita iterar sobre él una vez, puede eliminar la llamada a listpara que sea constante en términos de memoria.
lvc

Respuestas:

115

La forma Pythonic de sumar una matriz está usando sum. Para otros propósitos, a veces puede usar alguna combinación de reduce(del functoolsmódulo) y el operatormódulo, por ejemplo:

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

Tenga en cuenta que en reducerealidad es una foldl, en términos de Haskell. No hay una sintaxis especial para realizar pliegues, no hay una función incorporada foldry, en realidad, el uso reducecon operadores no asociativos se considera de mal estilo.

El uso de funciones de orden superior es bastante pitónico; hace un buen uso del principio de Python de que todo es un objeto, incluidas las funciones y clases. Tienes razón en que algunos Pythonistas desaprueban las lambdas, pero sobre todo porque tienden a no ser muy legibles cuando se vuelven complejas.

Fred Foo
fuente
4
@JBernardo: ¿estás diciendo que cualquier cosa que no esté en el módulo incorporado no es pitónica?
Fred Foo
4
No, sería una estupidez decirlo. Pero dame una sola razón por la que crees que GvR odiaría tanto la función de reducción en el punto de eliminarla de las funciones incorporadas.
JBernardo
6
@JBernardo: porque la gente intenta jugarle trucos demasiado inteligentes. Para citar esa publicación del blog, "la aplicabilidad de reduce()está bastante limitada a los operadores asociativos, y en todos los demás casos es mejor escribir el ciclo de acumulación explícitamente". Entonces, su uso es limitado, pero incluso GvR aparentemente tuvo que admitir que es lo suficientemente útil como para mantenerlo en la biblioteca estándar.
Fred Foo
13
@JBernardo, ¿eso significa que todos los usos de fold en Haskell y Scheme son igualmente malos? Es solo un estilo diferente de programación, ignorarlo y llevarse los dedos a los oídos y decir que no está claro no lo hace así. Como la mayoría de las cosas que tienen un estilo diferente, se necesita práctica para acostumbrarse . La idea es poner las cosas en categorías generales para que sea más fácil razonar sobre los programas. "Oh, quiero hacer esto, mmm, parece un pliegue" (o un mapa, o un despliegue, o un despliegue y luego un pliegue sobre eso)
Wes
3
Lambda en Python no puede contener más de una expresión. No puede hacerlo complejo incluso si se esfuerza. Entonces, los Pythonistas a quienes no les gustan probablemente simplemente no estén acostumbrados y, por lo tanto, no les guste el estilo de programación funcional.
golem
16

Haskell

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

Pitón

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

Obviamente, ese es un ejemplo trivial para ilustrar un punto. En Python simplemente lo haría sum([1,2,3,4,5])e incluso los puristas de Haskell generalmente preferirían sum [1,2,3,4,5].

Para escenarios no triviales cuando no hay una función de conveniencia obvia, el enfoque pitónico idiomático es escribir explícitamente el ciclo for y usar la asignación de variable mutable en lugar de usar reduceo a fold.

Ese no es en absoluto el estilo funcional, pero es la forma "pitónica". Python no está diseñado para puristas funcionales. Vea cómo Python favorece las excepciones para el control de flujo para ver qué tan no funcional es Python idiomático.

arcilla
fuente
12
los pliegues son útiles para más "puristas" funcionales. Son abstracciones de propósito general. Los problemas recurrentes son omnipresentes en la informática. Los pliegues ofrecen una forma de eliminar el texto estándar y una forma de hacer que las soluciones recursivas sean seguras en idiomas que no admiten la recursividad de forma nativa. Así que algo muy práctico. Los prejuicios de GvR en esta área son lamentables.
itsbruce
12

En Python 3, reducese ha eliminado: Notas de la versión . Sin embargo, puede utilizar el módulo de funciones

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

Por otro lado, la documentación expresa preferencia hacia for-loop en lugar de reduce, por lo tanto:

def product(xs):
    result = 1
    for i in xs:
        result *= i
    return result
Kyr
fuente
8
reduceno se eliminó de la biblioteca estándar de Python 3. reducemovido al functoolsmódulo como se muestra.
arcilla
@clay, acabo de tomar la frase de las notas de lanzamiento de Guido, pero puede que tengas razón :)
Kyr
6

A partir Python 3.8, y la introducción de expresiones de asignación (PEP 572) ( :=operador), que da la posibilidad de nombrar el resultado de una expresión, podemos usar una lista de comprensión para replicar lo que otros lenguajes llaman operaciones de plegar / plegar a la izquierda / reducir:

Dada una lista, una función reductora y un acumulador:

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

podemos doblar itemscon el ffin de obtener el resultado accumulation:

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

o en forma condensada:

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

Tenga en cuenta que esto también es una operación "scanleft" ya que el resultado de la comprensión de la lista representa el estado de la acumulación en cada paso:

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

También puedes reinventar la rueda:

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
fuente
Cambias los argumentos fen tu caso recursivo.
KayEss
7
Debido a que Python carece de recursividad de cola, esto romperá en listas más largas y es un desperdicio. Además, esta no es realmente la función "plegar", sino simplemente un pliegue a la izquierda, es decir, pliegue, es decir, exactamente lo que reduceya ofrece (tenga en cuenta que la firma de la función reduce es reduce(function, sequence[, initial]) -> value; también incluye la funcionalidad de dar un valor inicial para el acumulador).
cemper93
5

En realidad, no es la respuesta a la pregunta, pero sí frases para foldl y 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
fuente
2
Creo que esta es una mejor manera de escribir su foldr: reduce(lambda y, x: x**y, reversed(a)). Ahora tiene un uso más natural, funciona con iteradores y consume menos memoria.
Mateen Ulhaq
2

La respuesta real a este problema (de reducción) es: ¡Simplemente use un bucle!

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

Esto será más rápido que una reducción y cosas como PyPy pueden optimizar bucles como ese.

Por cierto, el caso de la suma debe resolverse con la sumfunción

JBernardo
fuente
5
Esto no se consideraría pitónico para un ejemplo como este.
jamylak
7
Los bucles de Python son notoriamente lentos. Usar (o abusar) reducees una forma común de optimizar un programa Python.
Fred Foo
2
@larsmans Por favor, no vengas a decir que reducir es más rápido que un simple bucle ... Siempre tendrá una sobrecarga de llamada de función para cada iteración. Además, nuevamente, Pypy puede optimizar los bucles a la velocidad C
JBernardo
1
@JBernardo: sí, eso es lo que estoy reclamando. Acabo de perfilar mi versión de productcontra uno en tu estilo, y es más rápido (aunque marginalmente).
Fred Foo
1
@JBernardo Asumiendo una función incorporada (como operator.add) como argumento para reducir: esa llamada adicional es una llamada C (que es mucho más barata que una llamada Python), y ahorra el envío e interpretación de un par de instrucciones de código de bytes, que fácilmente pueden causar docenas de llamadas a funciones.
1

Creo que algunos de los que respondieron a esta pregunta han pasado por alto la implicación más amplia de la foldfunción como herramienta abstracta. Sí, sumpuede hacer lo mismo con una lista de números enteros, pero este es un caso trivial. foldes más genérico. Es útil cuando tiene una secuencia de estructuras de datos de forma variable y desea expresar una agregación de forma limpia. Entonces, en lugar de tener que construir un forbucle con una variable agregada y volver a calcularlo manualmente cada vez, una foldfunción (o la versión de Python, que reduceparece corresponder) permite al programador expresar la intención de la agregación de manera mucho más sencilla simplemente proporcionando dos cosas:

  • Un valor inicial predeterminado o "semilla" para la agregación.
  • Una función que toma el valor actual de la agregación (comenzando con la "semilla") y el siguiente elemento de la lista, y devuelve el siguiente valor de agregación.
rq_
fuente
¡Hola rq_! Creo que su respuesta mejoraría y agregaría mucho si diera un ejemplo no trivial de foldque es difícil de hacer limpiamente en Python, y luego " fold" eso en Python :-)
Scott Skiles
0

Puede que llegue bastante tarde a la fiesta, pero podemos crear personalización foldrutilizando un cálculo lambda simple y una función de curry. Aquí está mi implementación de foldr en 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))

Aunque la implementación es recursiva (puede ser lenta), imprimirá los valores 15y 120respectivamente

Pantalón
fuente