Folds over Data.Map
johan.tibell at gmail.com
Mon Aug 23 09:03:02 EDT 2010
On Mon, Aug 23, 2010 at 11:40 AM, Gregory Collins
<greg at gregorycollins.net>wrote:
> Johan Tibell <johan.tibell at gmail.com> 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. :)
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries