language agnostic - ¿Cómo sabes cuándo usar fold-left y cuándo usar fold-right?

language-agnostic functional-programming

Question

Soy consciente de que doblar a la izquierda produce árboles de inclinación hacia la izquierda y doblar a la derecha produce árboles de inclinación derecha, pero cuando busco un pliegue, a veces me siento atrapado en un pensamiento que induce dolor de cabeza tratando de determinar qué tipo de pliegue es apropiado. Por lo general, termino desenrollando todo el problema y paso por la implementación de la función de plegado, ya que se aplica a mi problema.

Entonces, lo que quiero saber es:

• ¿Cuáles son algunas reglas generales para determinar si doblar hacia la izquierda o doblar hacia la derecha?
• ¿Cómo puedo decidir rápidamente qué tipo de doblez utilizar dado el problema que estoy enfrentando?

Hay un ejemplo en Scala por ejemplo (PDF) de usar un doblez para escribir una función llamada flatten que concatena una lista de listas de elementos en una sola lista. En ese caso, un doblez correcto es la elección correcta (dada la forma en que se concatenan las listas), pero tuve que pensarlo un poco para llegar a esa conclusión.

Como doblar es una acción tan común en la programación (funcional), me gustaría poder tomar este tipo de decisiones de forma rápida y con confianza. Entonces ... ¿Algún consejo?

Answer 1

Otros carteles han dado buenas respuestas y no repetiré lo que ya han dicho. Como ha dado un ejemplo de Scala en su pregunta, le daré un ejemplo específico de Scala. Como Tricks ya dijo, un foldRight necesita conservar n-1 stack frames, donde n es la longitud de su lista y esto puede conducir fácilmente a un desbordamiento de pila, y ni siquiera la recursividad de cola podría salvarlo de esto.

Una List(1,2,3).foldRight(0)(_ + _) se reduciría a:

1 + List(2,3).foldRight(0)(_ + _)        // first stack frame
    2 + List(3).foldRight(0)(_ + _)      // second stack frame
        3 + 0                            // third stack frame 
// (I don''t remember if the JVM allocates space 
// on the stack for the third frame as well)

mientras que List(1,2,3).foldLeft(0)(_ + _) se reduciría a:

(((0 + 1) + 2) + 3)

que se puede calcular iterativamente, como se hace en la implementación de List .

En un lenguaje estrictamente evaluado como Scala, un foldRight puede soplar fácilmente la pila para listas grandes, mientras que foldLeft no lo hará.

Ejemplo:

scala> List.range(1, 10000).foldLeft(0)(_ + _)
res1: Int = 49995000

scala> List.range(1, 10000).foldRight(0)(_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...

Mi regla general es por lo tanto: para los operadores que no tienen una asociatividad específica, siempre use foldLeft , al menos en Scala. De lo contrario, vaya con otros consejos dados en las respuestas;).

Answer 2

Puede transferir un pliegue en una notación de operador infijo (escribiendo entre ellos):

Este ejemplo se pliega usando la función de acumulador x

fold x [A, B, C, D]

por lo tanto, es igual

A x B x C x D

Ahora solo tiene que razonar sobre la asociatividad de su operador (¡poniendo entre paréntesis!).

Si tiene un operador asociativo de la izquierda , establecerá los paréntesis como este

((A x B) x C) x D

Aquí, usas un doblez a la izquierda . Ejemplo (pseudocódigo de estilo haskell)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

Si su operador es de asociación correcta ( doble derecha ), los paréntesis se establecerían así:

A x (B x (C x D))

Ejemplo: Cons-Operator

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

En general, los operadores aritméticos (la mayoría de los operadores) son asociativos de izquierda, por lo que foldl está más extendido. Pero en los otros casos, la notación infija + paréntesis es bastante útil.

Answer 3

También vale la pena señalar (y me doy cuenta de que esto indica lo obvio un poco), en el caso de un operador conmutativo, los dos son bastante equivalentes. En esta situación, un foldl podría ser la mejor opción:

foldl: (((1 + 2) + 3) + 4) puede calcular cada operación y llevar el valor acumulado hacia adelante

foldr: (1 + (2 + (3 + 4))) necesita un marco de pila para abrirse para 1 + ? y 2 + ? antes de calcular 3 + 4 , necesita retroceder y hacer el cálculo para cada uno.

No soy lo suficientemente experto en idiomas funcionales o en optimizaciones de compiladores para decir si esto realmente marcará una diferencia, pero ciertamente parece más limpio usar un foldl con operadores conmutativos.

Answer 4

Olin Shivers los diferenció diciendo "foldl es el iterador de la lista fundamental" y "foldr es el operador de recursión de la lista fundamental". Si nos fijamos en cómo funciona foldl:

((1 + 2) + 3) + 4

puedes ver el acumulador (como en una iteración recursiva en la cola) que se está construyendo. Por el contrario, foldr procede:

1 + (2 + (3 + 4))

donde puedes ver el recorrido al caso base 4 y construir el resultado desde allí.

Así que postulo una regla general: si parece una iteración de lista, una que sería simple de escribir en forma recursiva de cola, foldl es el camino a seguir.

Pero realmente esto será probablemente más evidente por la asociatividad de los operadores que está utilizando. Si son asociativos de izquierda, use foldl. Si tienen una asociación correcta, use foldr.