Folds over Data.Map

Johan Tibell johan.tibell at
Mon Aug 23 05:04:36 EDT 2010

Hi all,

After working on optimizing the folds defined in Data.Map, I'm not sure that
the current definitions are correct. In particular, `fold` is defined as

    -- | /O(n)/. Fold the values in the map, such that
    -- @'fold' f z == 'Prelude.foldr' f z . 'elems'@.
    -- For example,
    -- > elems map = fold (:) [] map
    -- > let f a len = len + (length a)
    -- > fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

It's not true that

    fold f z == foldr f z . elems

in general. It only holds if `z` is an identity for `f` as `z` is used at
every leaf in the tree.

Using a none identity element for `z` doesn't really work in practice as a
user cannot tell how many times `z` will be used, as it depends on the shape
of tree which in turn depends on how balanced it is at any given point.

Is there a better way to define folds over maps or should we just change the
documentation to say that you most likely want `z` to be an identity?

-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Libraries mailing list