Folds over Data.Map

[Johan Tibell]

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?

Cheers,
Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100823/414a714c/attachment.html