Yesterday I wrote something slightly unusual: module Storage where data Storage x instance Monad Storage run :: Storage x -> x data Key v instance Eq (Key v) instance Ord (Key v) new_key :: v -> Storage (Key v) set_key :: Key v -> v -> Storage () get_key :: Key v -> Storage (Maybe v) delete_key :: Key v -> Storage () In other words, you can store a value (of arbitrary type) under a unique key. The monad chooses what key for you, and tells you the key so you can look up or alter the value again later. Under the covers, it uses Data.Map to store stuff. I used some trickery with existential quantification and unsafeCoerce (!!) to make it work. Notice the sneaky phantom type in the key, telling the type system what type to coerce the value back to when you read it. Neat, eh? ...until I realised that somebody that somebody could generate a key in one run and then try to use it in another run. o_O Oops! But hey, until then it was working quite well. And completely pure; no IO anywhere. Ah well, just thought I'd share... (You could of course do away with the monad, but then you'd be able to manipulate the dictionary directly, and key uniqueness would be even more fragile!)