"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