¿Cómo saber cuándo usar el pliegue a la izquierda y cuándo usar el pliegue a la derecha?

Soy consciente de que doblar a la izquierda produce árboles que se inclinan a la izquierda y que doblar a la derecha produce árboles que se inclinan a la derecha, pero cuando alcanzo un pliegue, a veces me encuentro atascado en pensamientos que me provocan dolor de cabeza tratando de determinar qué tipo de pliegue. es apropiado. Por lo general, termino resolviendo todo el problema y avanzando paso a paso 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 a la izquierda o a la derecha?
• ¿Cómo puedo decidir rápidamente qué tipo de pliegue usar dado el problema al que me enfrento?

Hay un ejemplo en Scala by Example (PDF) de usar 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 a la derecha 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?

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]

así es igual

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í, usa un pliegue a la izquierda . Ejemplo (pseudocódigo estilo haskell)

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

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

Olin Shivers los diferenciaba diciendo que "foldl es el iterador de lista fundamental" y "foldr es el operador de recursividad de lista fundamental". Si miras cómo funciona foldl:

((1 + 2) + 3) + 4

puede ver el acumulador (como en una iteración recursiva de cola) en construcción. Por el contrario, foldr procede:

1 + (2 + (3 + 4))

donde puede 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 en realidad, esto probablemente será más evidente a partir de la asociatividad de los operadores que está utilizando. Si son asociativos por la izquierda, use foldl. Si son asociativos a la derecha, use foldr.

Otros carteles han dado buenas respuestas y no repetiré lo que ya han dicho. Como ha dado un ejemplo de Scala en su pregunta, daré un ejemplo específico de Scala. Como ya dijo Tricks , es foldRightnecesario preservar n-1los marcos de pila, dónde nestá 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.

A 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 deList .

En un lenguaje estrictamente evaluado como Scala, a foldRightpuede hacer volar fácilmente la pila para listas grandes, mientras foldLeftque a 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 general es: para los operadores que no tienen una asociatividad específica, utilice siempre foldLeft, al menos en Scala. De lo contrario, vaya con otros consejos dados en las respuestas;).

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 prácticamente 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 adelante el valor acumulado

foldr: (1 + (2 + (3 + 4)))necesita que se abra un marco de pila para 1 + ?y 2 + ?antes de calcular 3 + 4, luego 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 marcará la diferencia, pero ciertamente parece más limpio usar un pliegue con operadores conmutativos.