foldl, tail recursion, and strictness (was: stack overflow)

[C.Reinke]

"Julian Assange" <proff@iq.org>:
> ..
> | When used with a 170k input file, makemap suffers from a stack
> | overflow. foldl should be tail recursive. What's the score?

"Simon Peyton-Jones" <simonpj@microsoft.com>:
> Consider 
> 	foldl (+) 0 [x1,x2,x3,x4,...
> 
> This rewrites to
> 
> 	foldl (+) (0 + x1) [x2,x3,x4,...]
> =>	foldl (+) (0 + x1 + x2) [x3,x4,...]
> =>	foldl (+) (0 + x1 + x2 +x3) [x4,...]
> 
> And so on.  So we build up a giant chain of thunks.
> Finally we evaluate the giant chain, and that builds up
> a giant stack.

So foldl is indeed tail recursive, but this doesn't help if its
operator isn't strict because the tail recursion only builds up the
expression to be evaluated. Making strictness explicit by defining a
variant of foldl that evaluates its accumulator at each step helps to
solve the problem and documents programmer intentions.

This is quite common a trap for Haskellers to fall into (and was
certainly already considered well-known when I first saw it;-), so it
might be worth documenting it somewhere, and mentioning it in
introductory courses.

<plug>

You can see some of this using GHood 

  http://www.cs.ukc.ac.uk/people/staff/cr3/toolbox/haskell/GHood/

The three folds over lists (foldr, foldl, foldl') are one of the online
examples for GHood (in fact, foldl was mentioned as an example of the
potential use for animated observations in Andy Gill's Hood paper).  

If you stop the animation of the foldl example somewhere around step 40
(of 66), you can see that the spine of the input list has been observed
completely(!), and the functional parameter has been applied once for
each list element, but none of the applications has yet returned an
observable result. Instead, a long chain of yellow nodes indicates that
the observation of the end result depends on several intermediate
computations (such chains roughly indicate stack usage). The next step
will observe the second parameter to foldl, and from then on the chain
unwinds again, and only then the elements of the input list will be
observed..

</plug>

> Why can't GHC evaluate as it goes?  Because it's only
> correct to do so if the function is strict in its second argument,

..first argument..?-)

  foldl (\x y->y) (error "don't touch!") [1/0,2/0,3/0,4]
=> 4.0

Hth,
Claus