Proposal: Foldable typeclass: make foldl' and foldr' class methods

[Duncan Coutts]

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