Folds over Data.Map
Johan Tibell
johan.tibell at gmail.com
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?
Cheers,
Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100823/414a714c/attachment.html
More information about the Libraries
mailing list