foldRight Efficiency?

Question

I heard foldLeft is much more efficient in most of operations, but Scala School (from Twitter) gave the following example. Can someone give an analysis of its efficiency and should we achieve the same operation using 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

As you can see from the docs, List's foldRight and foldLeft methods are defined in LinearSeqOptimized. So take a look at the source:

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

So foldLeft uses a while-loop and foldRight uses a simple-recursive method. In particular it is not tail-recursive. Thus foldRight has the overhead of creating new stack frames and has a tendency to overflow the stack if you try it on a long list (try, for example ((1 to 10000).toList :\ 0)(_+_). Boom! But it works fine without the toList, because Range's foldRight works by reversing the folding left).

So why not always use foldLeft? For linked lists, a right fold is arguably a more natural function, because linked lists need to be built in reverse order. You can use foldLeft for your method above, but you need to reverse the output at the end. (Do not try appending to Lists in a left fold, as the complexity is O(n-squared).)

As for which is quicker in practice, foldRight or foldLeft + reverse, I ran a simple test and foldRight is faster for Lists by between 10 and 40 %. This must be why List's foldRight is implemented the way it is.