Folds over Data.Map

Gregory Collins greg at
Mon Aug 23 05:40:50 EDT 2010

Johan Tibell <johan.tibell at> writes:

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

Hey Johan,

    -- | /O(n)/. Post-order fold.
    foldr :: (k -> a -> b -> b) -> b -> Map k a -> b
    foldr _ z Tip              = z
    foldr f z (Bin _ kx x l r) = foldr f (f kx x (foldr f z r)) l

Note the third parameter to the recursive foldr call -- the "z" you see
at the Tips is not the same "z" that was originally passed in.

Gregory Collins <greg at>

More information about the Libraries mailing list