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