Various folds in the containers package
ekmett at gmail.com
Wed Jun 15 14:27:02 CEST 2011
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
> 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?
> Libraries mailing list
> Libraries at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries