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

[Jan-Willem Maessen]

On Aug 31, 2006, at 3:03 PM, Simon Peyton-Jones wrote: (replying to me)

>
> | 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:
> | ...
>
> Absolutely right.  This particular thing has been on my to-do list for
> at least 10 years (see Andy Gill's thesis).

In the interests of fairness I should point out that this was where I  
first saw this formulation (though it might have cropped up in some  
of Richard Bird's work).

The pH pass could do some other fancy footwork, like changing the  
handedness of a commutative fold and re-associating a nested fold of  
an associative operator.  That's all rather harder in the RULES  
framework (but I bet it's doable).  All that footwork also relied on  
getting the arity analysis right in the end.  I'm pretty convinced  
that arity munging was a critical enabling optimization.

-Jan



-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/glasgow-haskell-users/attachments/20060901/a08bd778/smime.bin