Various folds in the containers package

Edward Kmett ekmett at
Wed Jun 15 14:27:02 CEST 2011

On Wed, Jun 15, 2011 at 5:15 AM, Milan Straka <fox at> 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.
> There are several issues I am thinking about:
> a) we could left and right folds. For the Set and IntSet it is simple --
>   we can add foldr and foldl, and deprecated fold with the message 'use
>   foldr instead'.
>   For the Map and IntMap it is not so simple -- should we add both
>   foldr, foldl, foldlWithKey and foldrWithKey?
> b) we could use the Foldable instances more. We can implement foldr and
>   foldl efficiently and let the users to use those instead of providing
>   eg Set.foldr, Set.foldl.
>   This does not cover the *WithKey variant, as the Foldable instances
>   over Map and IntMap does not utilize the key.

In the keys package I have a notion of FoldableWithKey class that covers
this use case, defined over a large number of data types, but it can't be
used by containers as it requires a type family to talk about the container
key, and it would be nice to have raw material to link it to. ;) There is
also traverseWithKey.

> c) strict folds. If we add also strict folds, we would have a total of
>   _four_ folds in Set and IntSet and __eight__ folds in Map and IntMap.
>   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).
> 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?
> Cheers,
> Milan
> _______________________________________________
> Libraries mailing list
> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list