Various folds in the containers package

Edward Kmett ekmett at
Wed Jun 15 15:06:52 CEST 2011

On Wed, Jun 15, 2011 at 8:43 AM, Duncan Coutts <duncan.coutts at
> wrote:

> 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.

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).

I vaguely recall a discussion about adding them to the Foldable class with
the current definitions as defaults, but I don't think an actual
libraries at submission was ever made. I would definitely support this

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list