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
_______________________________________________
Glasgow-haskell-users mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
