Dynamic Map

[Lajos Nagy]

Hi,

Would it be possible to implement a Map in Haskell that, when
asked for a key it doesn't have, would return a 'fresh'
(meaning: not in the Map already) value, and afterwards it
would consistently return the same value for the given key.
In other words, it would behave like a dynamic map which
silently extends itself when someone asks for a non-existent
key.  If the user of this map only depends on the returned
value being different from the rest, then it's easy to
see that this dynamic map cannot break equational reasoning
so one would expect to be able to assign it a non-monadic
type:

lookup :: k -> DMap a -> a
insert :: k -> a -> DMap a -> DMap a

Of course, DMap cannot support certain operations because
that would break equational reasoning.  For example:

size :: DMap a -> Int

would depend on the order of lookups.  However, if
we restrict the operations to insert and lookup then
ER is restored.  (And those two operations is all I
need.)

I tried several ways of implementing it but those
monadic types just kept cropping up in the map interface.

I'd appreciate any ideas or pointers.

Regards,

Lajos Nagy