Various folds in the containers package

[Edward Kmett]

On Wed, Jun 15, 2011 at 5:15 AM, Milan Straka <fox at ucw.cz> 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 haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110615/fc27283a/attachment.htm>