foldRight Efficiency?

Question

Ho sentito che foldLeft è molto più efficiente nella maggior parte delle operazioni, ma Scala School (da Twitter) ha fornito il seguente esempio. Qualcuno può dare un'analisi della sua efficienza e dovremmo ottenere la stessa operazione 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

Come si può vedere dai documenti, i metodi foldRight e foldLeft di List sono definiti in . Quindi uno sguardo alla fonte:

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

Così foldLeft utilizza un ciclo while e foldRight utilizza un metodo semplice ricorsivo. In particolare non è coda-ricorsiva. Pertanto, foldRight ha il sovraccarico di creare nuovi frame stack e ha la tendenza a sovrasfruttare lo stack se lo si prova su un lungo elenco (prova, ad esempio ((1 to 10000).toList :\ 0)(_+_). Boom! Ma funziona senza lo , perché Range di foldRight funziona invertire il piegamento a sinistra).

Quindi perché non utilizzare sempre foldLeft? Per gli elenchi collegati, una piega a destra è probabilmente una funzione più naturale, poiché gli elenchi collegati devono essere costruiti in ordine inverso. È possibile utilizzare foldLeft per il metodo sopra, ma è necessario reverse l'output alla fine. (Non cercare aggiungendo alle liste in una piega a sinistra, come la complessità è O (n-squared).)

quanto per i quali è più veloce, in pratica, foldRight o foldLeft + reverse, ho eseguito un semplice test e foldRight è più veloce per gli elenchi tra il 10 e il 40%. Questo deve essere il motivo per cui FoldRight di List viene implementato così com'è.

Answer 2

foldRight inverte l'elenco e applica foldLeft.