Scala: Why will a right folding on a List cause stack overflow whereas not for a left folding?

Question

I ran a right folding (:\) on a List of String, which caused a stack overflow. But When I changed it to use a left folding (/:), it worked fine. Why?

Answer 1

Since the source is open, you can actually see the implementations in LinearSeqOptimized.scala:

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

What you will notice is that foldLeft uses a while-loop while foldRight uses recursion. The loop strategy is very efficient but recursion requires pushing a frame on the stack for every element in the list (as it traverses to the end). This is why foldLeft works fine but foldRight causes a stack overflow.

Answer 2

Fold are a general set of commonly used functions which traverse recursive data structures and typically result in a single value (reference). On sequences and lists, FoldLeft (in a general sense) is tail-recursive and as such, it can be optimized. FoldRight is not tail-recursive and thus can not be tail-call optimized. It does potentially have the benefit of being able to be applied to infinite series however.

The implementation of foldLeft and foldRight from the scala libraries (pirated from @dhg's answer) reflect this optimization/lack-there-of. foldLeft has been manually tail-call optimized using a while loop. foldRight can not be.

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

I believe there is a section in Programming in Scala, Second Edition by Odersky, Spoon, Venners on folds which describes how foldLeft on Lists is tail-recursive while it may be possible to foldRight on infinite lists. Unfortunately, I do not have it on me at the moment in order to provide page numbers, etc. If not, it isn't very difficult to prove this.

See also the section of folds in Learn You a Haskell for Great Good by Miran Lipovača

Back when we were dealing with recursion, we noticed a theme throughout many of the recursive functions that operated on lists. Usually, we'd have an edge case for the empty list. We'd introduce the x:xs pattern and then we'd do some action that involves a single element and the rest of the list. It turns out this is a very common pattern, so a couple of very useful functions were introduced to encapsulate it. These functions are called folds.