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