Why does Haskell's foldr NOT stackoverflow while the same Scala implementation does?

Question

I am reading FP in Scala.

Exercise 3.10 says that foldRight overflows (See images below). As far as I know , however foldr in Haskell does not.

http://www.haskell.org/haskellwiki/

-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

How is this different behaviour possible?

What is the difference between the two languages/compilers that cause this different behaviour?

Where does this difference come from ? The platform ? The language? The compiler?

Is it possible to write a stack-safe foldRight in Scala? If yes, how?

Answer 1

Haskell is lazy. The definition

foldr f z (x:xs) = f x (foldr f z xs)

tells us that the behaviour of foldr f z xs with a non-empty list xs is determined by the laziness of the combining function f.

In particular the call foldr f z (x:xs) allocates just one thunk on the heap, {foldr f z xs} (writing {...} for a thunk holding an expression ...), and calls f with two arguments - x and the thunk. What happens next, is f's responsibility.

In particular, if it's a lazy data constructor (like e.g. (:)), it will immediately be returned to the caller of the foldr call (with the constructor's two slots filled by (references to) the two values).

And if f does demand its value on the right, with minimal compiler optimizations no thunks should be created at all (or one, at the most - the current one), as the value of foldr f z xs is immediately needed and the usual stack-based evaluation can used:

foldr f z [a,b,c,....,n] ==
    a `f` (b `f` (c `f` (... (n `f` z)...)))

So foldr can indeed cause SO, when used with strict combining function on extremely long input lists. But if the combining function doesn't demand right away its value on the right, or only demands a part of it, the evaluation will be suspended in a thunk, and the partial result as created by f will be immediately returned. Same with the argument on the left, but they already come as thunks, potentially, in the input list.

Answer 2

Haskell is lazy. So foldr allocates on the heap, not the stack. Depending on the strictness of the argument function, it may allocate a single (small) result, or a large structure.

You're still losing space, compared to a strict, tail-recursive implementation, but it doesn't look as obvious, since you've traded stack for heap.

Answer 3

Note that the authors here are not referring to any foldRight definition in the scala standard library, such as the one defined on List. They are referring to the definition of foldRight they gave above in section 3.4.

The scala standard library defines the foldRight in terms of foldLeft by reversing the list (which can be done in constant stack space) then calling foldLeft with the the arguments of the passed function reversed. This works for lists, but won't work for a structure which cannot be safely reversed, for example:

scala> Stream.continually(false)
res0: scala.collection.immutable.Stream[Boolean] = Stream(false, ?)

scala> res0.reverse
java.lang.OutOfMemoryError: GC overhead limit exceeded

Now lets think about what should be the result of this operation:

Stream.continually(false).foldRight(true)(_ && _)

The answer should be false, it doesn't matter how many false values are in the stream or if it is infinite, if we are going to combine them with a conjunction, the result will be false.

haskell of course gets this with no problem:

Prelude> foldr (&&) True (repeat False)
False

And that is because of two important things: haskell's foldr will traverse the stream from left to right, not right to left, and haskell is lazy by default. The first item here, that foldr actually traverses the list from left to right might surprise or confuse some people who think of a right fold as starting from the right, but the important feature of a right fold is not which end of a structure it starts on, but in which direction the associativity is. So give a list [1,2,3,4] and an op named op, a left fold is

((1 op 2) op 3) op 4)

and a right fold is

(1 op (2 op (3 op 4)))

But the order of evaluation shouldn't matter. So what the authors have done here in chapter 3 is to give you a fold which traverses the list from left to right, but because scala is by default strict, we still will not be able to traverse our stream of infinite falses, but have some patience, they will get to that in chapter 5 :) I'll give you a sneak peek, lets look at the difference between foldRight as it is defined in the standard library and as it is defined in the Foldable typeclass in scalaz:

Here's the implementation from the scala standard library:

def foldRight[B](z: B)(op: (A, B) => B): B

Here's the definition from scalaz's Foldable:

def foldRight[B](z: => B)(f: (A, => B) => B): B

The difference is that the Bs are all lazy, and now we get to fold our infinite stream again, as long as we give a function which is sufficiently lazy in its second parameter:

scala> Foldable[Stream].foldRight(Stream.continually(false),true)(_ && _)
res0: Boolean = false