Various folds in the containers package

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


On Wed, Jun 15, 2011 at 8:43 AM, Duncan Coutts <duncan.coutts at googlemail.com
> 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
motion.

-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110615/b5693921/attachment.htm>


More information about the Libraries mailing list