foldRight Efficiency?

Question

Escuché que foldLeft es mucho más eficiente en la mayoría de las operaciones, pero la Scala School (de Twitter) dio el siguiente ejemplo. ¿Puede alguien dar un análisis de su eficiencia y deberíamos lograr la misma operación usando foldLeft?

val numbers = List(1,2,3,4,5,...10) 
def ourMap(numbers: List[Int], fn: Int => Int): List[Int] = { 
    numbers.foldRight(List[Int]()) { (x: Int, xs: List[Int]) => 
    fn(x) :: xs 
    } 
} 

scala> ourMap(numbers, timesTwo(_)) 
res0: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20) 

Answer 1

Como puede ver en los documentos, List's fold Los métodos right y foldLeft se definen en LinearSeqOptimized. Así que eche un vistazo a la fuente:

override /*TraversableLike*/ 
def foldLeft[B](z: B)(f: (B, A) => B): B = { 
    var acc = z 
    var these = this 
    while (!these.isEmpty) { 
    acc = f(acc, these.head) 
    these = these.tail 
    } 
    acc 
} 

override /*IterableLike*/ 
def foldRight[B](z: B)(f: (A, B) => B): B = 
    if (this.isEmpty) z 
    else f(head, tail.foldRight(z)(f)) 

Así foldLeft utiliza un bucle while y foldRight utiliza un método sencillo recursiva. En particular, no es recursivo en la cola. Por lo tanto, foldRight tiene la ventaja de crear nuevos marcos de pila y tiende a desbordar la pila si lo prueba en una lista larga (intente, por ejemplo, ((1 to 10000).toList :\ 0)(_+_). ¡Boom! Pero funciona bien sin toList, porque Range's foldRight funciona por invirtiendo el plegado a la izquierda).

¿Por qué no siempre usar foldLeft? Para las listas vinculadas, un doblez correcto es posiblemente una función más natural, porque las listas vinculadas deben construirse en orden inverso. Puede usar foldLeft para su método anterior, pero necesita reverse la salida al final. (No intente añadiendo a las listas en un pliegue izquierda, ya que la complejidad es O (n-cuadrado).)

En cuanto a cuál es más rápido en la práctica, foldRight o foldLeft + reverse, me encontré con una prueba simple y foldRight es más rápido para las listas entre 10 y 40%. Esta debe ser la razón por la que foldRight de List se implementa de la manera que es.

Answer 2

foldRight invierte la lista y aplica foldLeft.