On Mon, 2011-06-20 at 19:08 +0100, Paterson, Ross wrote:
It's a pity to have to add methods to get around GHC's limitations, but it seems harmless.
It's true, though I don't think it's a trivial limitation. The required analysis and transform is described by Andy Gill in his thesis (where it's needed so that you can fuse foldl-defined-in-terms-of-foldr using foldr/build fusion) and it's not been implemented in the 15 years since. Though GHC HEAD does currently have a "simple" implementation of the arity raising transformation but I don't think anyone has yet seriously investigated if it'd cover these kinds of cases. I was about to say that direct implementations of foldl' and foldr' can be improved compared to foldl and foldr because types like arrays and Data.Sequence can implement some of them as reverse traversals, but actually that'd work already since foldl' is a foldr and foldr' is a foldl, so an implementation of foldl as a reverse traversal would give a reasonable foldr' (apart from the higher order vs accumulator business).
Looks like you'll want strict versions of all 5 methods, though.
Mm, the '1' variants are obvious. The fold and foldMap are more interesting. I'd have to think harder about what their default definition would be, or what specialised implementations might look like (e.g. tree folds starting from the leaves and working towards the root). Are there any obvious use cases for strict monoid folds? Duncan