Various folds in the containers package

[Duncan Coutts]

On Wed, 2011-06-15 at 11:15 +0200, Milan Straka wrote:
> Hi all,
> 
> currently we have the following folds in the containers package:
> Map: fold, foldWithKey, foldrWithKey, foldlWithKey
> Set: fold
> IntMap; fold, foldWithKey
> IntSet: fold
> 
> If the direction (right, left) is not specified, the fold is the right
> fold. So currently we have no left folds (except for the Map) and also
> Map and IntMap are not consistent.

My recommendation is that we add all four folds:

foldr, foldl'
foldl, foldr'

Don't get confused with thinking about the "direction". Direction is an
implementation issue (albeit an important one). As you know, the 'l' and
'r' in foldl and foldr are not direction but the left or right
bracketing of the operations.

left bracketing:  ((0 + x_0) + x_1) + x_2
right bracketing: x_0 + (x_1 + (x_2 + 0))

Then the strictness is whether we reduce to WHNF before applying the
operator.

So I think those are the appropriate function names and abstract
definitions, because they correspond to what we're all used to with
lists. The implicit order of the order of the set/map keys, low to high.

Now, when it comes to implementation the direction is important. The
foldr and foldl' functions are best implemented as forwards/ascending
traversals while foldl and foldr' are best implemented as
backwards/descending traversals.

In particular note that we can write things like:

biggest = foldl (\y x -> x) undefined

and evaluate it in O(log n) time. We get "early exit" behaviour.

So by having all four traversals we cover the use cases where people
want folds that start "from the back" (thinking about it operationally).

>    The Foldable module exports foldl' and foldr', which use foldr, foldl
>    respectively, but needs some intermediate memory (it creates a thunk
>    for every node of the structure). Apart from that, this does not
>    cover the *WithKey variants as in b).

This is unfortunate. For data structures with equal access to all
elements (arrays, map/set etc) we can implement foldl' and foldr'
directly and more efficiently.

> Personally I would add foldr, foldl, foldlWithKey, foldrWithKey and
> specialised foldr, foldl implementations in the Foldable classes.
> I am not sure about the strict folds -- I used an equivalent of the
> foldr' from the Foldable module in GHC and it was reasonable fast.
> 
> Any oppinions?

So I suggest all four folds. They are all useful and can all be
implemented efficiently.

Perhaps you need the withKey variety too. Do provide a Foldable
instance, and perhaps later we can lobby for foldl' and foldr' to be
made members of the Foldable class rather than fixed definitions in
terms of foldl and foldr (bytestring, vector and text could benefit from
this too).

Duncan