scala - spark - foldLeft v. foldRight-¿Importa?

foldleft spark

Question

Anteriormente, Nicolas Rinaudo respondió mi pregunta sobre el Plegado de la Lista de Scala ¿Siempre utilizando foldLeft?

Al estudiar Haskell actualmente, entiendo que foldRight debe preferirse a foldLeft en los casos en que :: (prepend) se puede usar sobre ++ (append).

El motivo, según entiendo, es el rendimiento: el primero ocurre en O(1) , es decir, se agrega un elemento al frente, el tiempo constante. Mientras que el último requiere O(N) , es decir, pasar por la lista completa y agregar un elemento.

En Scala, dado que foldLeft se implementa en términos de foldRight , ¿el beneficio de usar :+ sobre ++ con foldRight importa incluso desde que foldRight se invierte, y luego foldLeft''d ?

Como ejemplo, considere esta simple operación de fold.. para simplemente devolver los elementos de una lista en orden.

foldLeft pliega sobre cada elemento, agregando cada elemento a la lista a través de :+ .

scala> List("foo", "bar").foldLeft(List[String]()) {
(acc, elem) => acc :+ elem }
res9: List[String] = List(foo, bar)

foldRight realiza un operador foldLeft with :: en cada elemento, pero luego invierte.

scala> List("foo", "bar").foldRight(List[String]()) {
(elem, acc) => elem :: acc }
res10: List[String] = List(foo, bar)

En realidad, ¿importa en Scala qué foldLeft o foldRight usar dado que foldRight usa foldRight ?

Answer 1

La respuesta de @Rein Henrichs es irrelevante para Scala, porque la implementación de foldLeft y foldRight por parte de Scala es completamente diferente (para empezar, Scala tiene una evaluación entusiasta).

foldLeft y foldRight tienen muy poco que ver con el rendimiento de su programa. Ambos son (liberalmente hablando) O (n * c_f) donde c_f es la complejidad de una llamada a la función f que se da. foldRight es más lento por un factor constante debido al reverse adicional, sin embargo.

Entonces, el factor real que diferencia uno de otro es la complejidad de la función anónima que usted brinda. A veces, es más fácil escribir una función eficiente diseñada para funcionar con foldLeft , y algunas veces para foldRight . En su ejemplo, la versión de foldRight es la mejor, porque la función anónima que le da a foldRight es O (1). Por el contrario, la función anónima que le das a foldLeft es O (n) en sí (amortizada, que es lo que importa aquí), porque acc sigue creciendo de 0 a n-1, y añadiendo a una lista de n elementos es O (n )

Por lo tanto, realmente importa si elige foldLeft o foldRight , pero no debido a estas funciones en sí mismas, sino debido a las funciones anónimas que se les otorgan. Si ambos son equivalentes, elija foldLeft por defecto.

Answer 2

No soy un experto en Scala, pero en Haskell, una de las características diferenciadoras más importantes entre foldl'' (que realmente debería ser el doblez predeterminado) y foldr es que foldr funcionará en estructuras de datos infinitas, donde foldl'' colgará indefinidamente.

Para entender por qué esto es así, recomiendo visitar foldl.com y foldr.com , expandir las evaluaciones un par de veces y reconstruir el árbol de llamadas. Verás rápidamente dónde foldr es apropiado versus foldl'' .

Answer 3

Puedo proporcionar una respuesta para Haskell, pero dudo que sea relevante para Scala:

Comencemos con la fuente para ambos,

foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Ahora, veamos dónde aparece la llamada recursiva a foldl o foldr en el lado derecho. Para foldl, es más externo. Para foldr, está dentro de la aplicación de f. Esto tiene un par de implicaciones importantes:

1. Si f es un constructor de datos, ese constructor de datos será el más a la izquierda, el más externo con foldr. Esto significa que foldr implementa la recursión protegida , de modo que lo siguiente es posible:

   > take 5 . foldr (:) [] $ [1..]
   [1,2,3,4]

   Esto significa que, por ejemplo, foldr puede ser un buen productor y un buen consumidor para la fusión de atajo . (Sí, foldr (:) [] es un morfismo de identidad para listas).

   Esto no es posible con foldl porque el constructor estará dentro de la llamada recursiva a foldl y no se puede emparejar el patrón.

2. Por el contrario, debido a que la llamada recursiva a foldl está en la posición extrema más a la izquierda, se reducirá mediante evaluación diferida y no ocupará espacio en la pila de coincidencia de patrones. Combinado con la anotación de rigor adecuada (por ejemplo, foldl'' ), esto permite que funciones como sum o length ejecuten en espacio constante.

Para más información sobre esto, vea Lazy Evaluation of Haskell .

Answer 4

De hecho, importa si usa foldLeft o foldRight en Scala, al menos con listas, al menos en la implementación predeterminada. Sin embargo, creo que esta respuesta no es válida para bibliotecas como Scalaz.

Si observa el código fuente de foldLeft y foldRight para LinearSeqOptimized , verá que:

• foldLeft se implementa con un bucle y variables mutables locales, y se ajusta en un marco de pila.
• foldRight es recursivo, pero no recursivo de cola, y por lo tanto consume un marco de pila por elemento en la lista.

foldLeft es seguro, mientras que foldRight puede foldRight desbordamiento para listas largas.

Editar Para completar mi respuesta, ya que solo hace referencia a una parte de su pregunta: también importa cuál use según lo que pretenda hacer.

Para tomar su ejemplo, lo que considero la solución óptima es usar foldLeft , foldLeft resultados a su acumulador, e reverse el resultado.

De esta manera:

• toda la operación es O (n)
• no desbordará la pila, independientemente del tamaño de la lista

Esto es esencialmente lo que pensaste que estabas haciendo con foldRight al asumir que se implementó en términos de foldLeft .

Si usa foldRight , obtendrá una implementación un poco más rápida (bueno, ligeramente ... el doble de rápido, realmente, pero aún O (n)) a costa de la seguridad.

Se podría argumentar que, si sabes que tus listas serán lo suficientemente pequeñas, no hay problemas de seguridad y puedes usar foldRight . Siento, pero eso es solo una opinión, que si tus listas son lo suficientemente pequeñas para que no tengas que preocuparte por tu stack, son lo suficientemente pequeñas para que no tengas que preocuparte por el rendimiento.

Answer 5

Depende, considere lo siguiente:

scala> val l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)
scala> l.foldLeft(List.empty[Int]) { (acc, ele) => ele :: acc }
res0: List[Int] = List(3, 2, 1)
scala> l.foldRight(List.empty[Int]) { (ele, acc) => ele :: acc }
res1: List[Int] = List(1, 2, 3)

Como puede ver, foldLeft atraviesa la lista desde la head hasta el último elemento. foldRight por otro lado, lo atraviesa desde el último elemento hasta la head .

Si usa plegado para la agregación, no debería haber diferencia:

scala> l.foldLeft(0) { (acc, ele) => ele + acc }
res2: Int = 6
scala> l.foldRight(0) { (ele, acc) => ele + acc }
res3: Int = 6