Lajos Nagy wrote:

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.

You could use unsafePerformIO, if it doesn't make you feel dirty. Here's what I do to achieve sharing of strings when parsing large files: import Data.HashTable as H import System.IO.Unsafe (unsafePerformIO) {-# NOINLINE stringPool #-} stringPool :: HashTable String String stringPool = unsafePerformIO $ new (==) hashString {-# NOINLINE shareString #-} shareString :: String -> String shareString s = unsafePerformIO $ do mv <- H.lookup stringPool s case mv of Just s' -> return s' Nothing -> do H.insert stringPool s s return s It seems to work, but if any GHC gurus notice any problems, please let me know. OT: This one feels pretty fast, does anyone have a more efficient implementation? /Björn