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 don't know what happened to the original proposal, but I was going to try something similar, with something like

data HashMap k v = HM !Int !(Tree k v)

insert k v (HM sz tree) = case search k tree of
    (Nothing, loc) -> HM (sz + 1) (assign v loc)
    (Just _, loc) -> HM sz (assign v loc)

Louis Wasserman
wasserman.louis@gmail.com
http://profiles.google.com/wasserman.louis


On Tue, Feb 22, 2011 at 8:45 PM, Johan Tibell <johan.tibell@gmail.com> wrote:
On Tue, Feb 22, 2011 at 6:28 PM, Louis Wasserman
<wasserman.louis@gmail.com> wrote:
> Apologies!

Accepted. :)

> I was, in point of fact, working on such a patch, but I think I've been
> convinced that it's a legitimate position for a package to take.  (I'm also
> curious, Johann, about the approach you figured out that didn't cost a word
> per node!)

I'm working on a patch that provides O(1) size right now. The trick is
to define HashMap as:

data HashMap k v = HM {-# UNPACK #-} !Int !(Tree k v)

data Tree k v
   = Nil
   | Tip {-# UNPACK #-} !Hash
         {-# UNPACK #-} !(FL.FullList k v)
   | Bin {-# UNPACK #-} !Prefix
         {-# UNPACK #-} !Mask
         !(Tree k v)
         !(Tree k v)

And have insert, delete, and other operations that change the size
return both the updated tree and the size delta (-1, 0, or 1 in the
case of insert/delete). The size delta is then applied to the stored
size.

At the moment I'm trying to figure out the performance impact of
making this change.

Johan