On Tue, Feb 22, 2011 at 6:53 PM, Louis Wasserman
Here's the approach I was attempting: a while back there was a proposal to modify Data.Map to support a sort of zipper, including the following API:
data Location k a -- represents a map with a "hole" at a particular key
search :: k -> Map k a -> (Maybe a, Location k a)
key :: Location k a -> k
assign :: a -> Location k a -> Map k a clear :: Location k a -> Map k a
and from here you might define
insert :: k -> a -> Map k a -> Map k a insert k a m = case search k m of (_, loc) -> assign a loc
The surprising thing was that this approach *increased* the speed of the Map implementation by something like 7%.
I'm pretty sure it was a decrease overall. The function under discussion was something like insertWith. The direct implementation of insertWith was the fastest. The zipper approach was 7% faster than using a naive composition of lookup and insert to implement insertWith. The slowdown was most likely caused by the extra O(log n) allocations required to create the zipper (in essence that means reify the call stack of lookup). Johan