¿Cómo saber cuándo usar fold-left y cuándo usar fold-right?

Question

Soy consciente de que el pliegue a la izquierda produce árboles inclinados a la izquierda y el pliegue a la derecha produce árboles que se inclinan a la derecha, pero cuando alcanzo un pliegue, a veces me encuentro atascado en un pensamiento inductor de dolor de cabeza tratando de determinar qué tipo de pliegue es apropiado. Por lo general, termino desenrollando todo el problema y avanzando en la implementación de la función de plegado según 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 hacia la derecha?
• ¿Cómo puedo decidir rápidamente qué tipo de pliegue usar dado el problema que estoy enfrentando?

Hay un ejemplo en Scala por ejemplo (PDF) de usando un pliegue para escribir una función llamada aplanar que concatena una lista de listas de elementos en una sola lista. En ese caso, un pliegue derecho 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.

Dado que el plegado 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 segura. Entonces ... ¿algún consejo?

Answer 1

Puede transferir un pliegue a una notación de operador infijo (escribiendo en el medio):

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

fold x [A, B, C, D]

por lo tanto es igual a

A x B x C x D

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

Si tiene un operador asociativo a la izquierda , establecerá los paréntesis de esta manera

((A x B) x C) x D

Aquí, utiliza un pliegue izquierdo . Ejemplo (pseudocódigo de estilo haskell)

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

Si su operador es asociativo a la derecha ( plegado a la derecha ), los paréntesis se establecerán 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 a la izquierda, por lo que foldl está más extendido. Pero en los otros casos, la notación infija + paréntesis es bastante útil.

Answer 2

Olin Shivers los diferencia al decir " foldl is el iterador de lista fundamental " y "foldr es el operador de recursión de lista fundamental". Si observa cómo funciona foldl:

((1 + 2) + 3) + 4

puede ver el acumulador (como en una iteración recursiva de cola) que se está construyendo. Por el contrario, foldr continúa:

1 + (2 + (3 + 4))

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

Entonces, propongo una regla de oro: si parece una iteración de lista, una que sería fácil de escribir en forma recursiva de cola, foldl es el camino a seguir.

Pero en realidad esto probablemente será más evidente por la asociatividad de los operadores que está utilizando. Si son asociativos a la izquierda, use foldl. Si son asociativos a la derecha, use foldr.

Answer 3

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 ya ha dicho Trucos , un foldRight necesita preservar n-1 marcos de pila, donde n es la longitud de su lista y esto puede conducir fácilmente a un desbordamiento de pila, y ni siquiera la recursión 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 de forma iterativa, como se hace en implementación de List .

En un lenguaje estrictamente evaluado como Scala, un foldRight puede explotar fácilmente la pila para listas grandes, mientras que un 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...

Por lo tanto, mi regla de oro es: 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 4

También vale la pena señalar (y me doy cuenta de que esto es un poco obvio), en el caso de un operador conmutativo, los dos son más o menos equivalentes. En esta situación, un pliegue 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 que se abra un marco de pila para 1 +? y 2 +? antes calculando 3 + 4 , entonces necesita regresar y hacer el cálculo para cada uno.

No soy lo suficientemente experto en lenguajes funcionales u optimizaciones de compiladores para decir si esto realmente hará la diferencia, pero ciertamente parece más limpio usar un pliegue con operadores conmutativos.