On Tue, Feb 22, 2011 at 6:53 PM, Louis Wasserman <[email protected]> wrote: > 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
