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

99

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?

Jeff
fuente
1
parece similar a stackoverflow.com/questions/384797/…
Steven Huwig
1
Esta Q es más general que la que trataba específicamente de Haskell. La pereza marca una gran diferencia en la respuesta a la pregunta.
Chris Conway
Oh. Extraño, de alguna manera pensé que vi una etiqueta de Haskell en esta pregunta, pero supongo que no ...
ephemient

Respuestas:

105

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.

Darío
fuente
6
Bueno, lo que describiste son en realidad foldl1y foldr1en Haskell ( foldly foldrtoma un valor inicial externo), y los "contras" de Haskell (:)no se llaman (::), pero por lo demás esto es correcto. Es posible que desee agregar que Haskell también proporciona un foldl'/ foldl1'que son variantes estrictas de foldl/ foldl1, porque la aritmética perezosa no siempre es deseable.
Ephemient
Lo siento, pensé que vi una etiqueta "Haskell" en esta pregunta, pero no está allí. Mi comentario realmente no tiene mucho sentido si no es Haskell ...
ephemient
@ephemient Lo viste. Es un "pseudocódigo estilo haskell". :)
smiling_man
La mejor respuesta que he visto relacionada con la diferencia entre pliegues.
AleXoundOS
60

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.

Steven Huwig
fuente
29

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;).

Flaviu Cipcigan
fuente
13
Esto era cierto anteriormente, pero en las versiones actuales de Scala, se ha cambiado foldRight para aplicar foldLeft en una copia invertida de la lista. Por ejemplo, en 2.10.3, github.com/scala/scala/blob/v2.10.3/src/library/scala/… . Parece que este cambio se realizó a principios de 2013: github.com/scala/scala/commit/… .
Dhruv Kapoor
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 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.


fuente
1
Los marcos de pila adicionales definitivamente marcarán la diferencia para listas grandes. Si sus marcos de pila exceden el tamaño de la caché del procesador, entonces sus fallas de caché afectarán el rendimiento. A menos que la lista esté doblemente vinculada, es un poco difícil hacer que foldr sea una función recursiva de cola, por lo que debe usar foldl a menos que haya una razón para no hacerlo.
A. Levy
4
La naturaleza perezosa de Haskell confunde este análisis. Si la función que se está plegando no es estricta en el segundo parámetro, entonces foldrpuede ser más eficiente foldly no requerirá marcos de pila adicionales.
Ephemient
2
Lo siento, pensé que vi una etiqueta "Haskell" en esta pregunta, pero no está allí. Mi comentario no tiene mucho sentido si no es Haskell ...
ephemient