Re: Folds over Data.Map

On Mon, Aug 23, 2010 at 11:40 AM, Gregory Collins wrote:

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

You're of course right. I can get back to my optimizing. :)