Various folds in the containers package

Milan Straka fox at ucw.cz
Wed Jun 15 11:15:37 CEST 2011


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.

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



More information about the Libraries mailing list