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

Answer 4

One easy way to demonstrate this in Haskell is to use equational reasoning to demonstrate lazy evaluation. Let's write the find function in terms of foldr:

-- Return the first element of the list that satisfies the predicate, or `Nothing`.
find :: (a -> Bool) -> [a] -> Maybe a
find p = foldr (step p) Nothing 
    where step pred x next = if pred x then Just x else next

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

In an eager language, if you wrote find with foldr it would traverse the whole list and use O(n) space. With lazy evaluation, it stops at the first element that satisfies the predicate, and uses only O(1) space (modulo garbage collection):

find odd [0..]
    == foldr (step odd) Nothing [0..]
    == step odd 0 (foldr (step odd) Nothing [1..])
    == if odd 0 then Just 0 else (foldr (step odd) Nothing [1..])
    == if False then Just 0 else (foldr (step odd) Nothing [1..])
    == foldr (step odd) Nothing [1..]
    == step odd 1 (foldr (step odd) Nothing [2..])
    == if odd 1 then Just 1 else (foldr (step odd) Nothing [2..])
    == if True then Just 1 else (foldr (step odd) Nothing [2..])
    == Just 1

This evaluation stops in a finite number of steps, in spite of the fact that the list [0..] is infinite, so we know that we're not traversing the whole list. In addition, there is an upper bound on the complexity of the expressions at each step, which translates into a constant upper bound on the memory required to evaluate this.

The key here is that the step function that we're folding with has this property: no matter what the values of x and next are, it will either:

1. Evaluate to Just x, without invoking the next thunk, or
2. Tail-call the next thunk (in effect, if not literally).