[GHC] #876: stack overflow on 'length . filter odd $ [0.. 999999999]'

[Simon Peyton-Jones]

| Actually, it's sufficient to do good arity-raising transformations,
| and use the definition:
|    foldl f z xs = foldr (\x k a -> k (f a x)) id xs z
| 
| This yields code which looks a bit like this:
| 
| let loop [] = id
|      loop (x:xs) = let k = loop xs in (\a -> k (f a x))
| in  loop xs z
| 
| In the pH compiler we recognized this idiom (and its generalizations
| to multiple accumulating parameters) and arity-raised loop as follows:
| 
| let loop []     a = a
|      loop (x:xs) a = loop xs (f a x)
| in  loop xs z

Absolutely right.  This particular thing has been on my to-do list for
at least 10 years (see Andy Gill's thesis).  Dana Xu and I worked on it
a bit last year, but her focus has shifted to verifying Haskell
programs.  We identified two analyses to help with arity raising: the
simpler one works by looking a function *definitions*, and will deal
with this example; the other looks at function *calls*.  

The good news is that Kirsten Chevalier is coming to Microsoft for an
internship Oct-Dec this year, and we plan to work on exactly this.
Watch this space.

Simon