Dynamic Map

[Bjorn Bringert]

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