On Fri, Mar 11, 2011 at 8:18 PM, Joshua Ball wrote:

Suppose I want the following functions:

newRef :: a -> RefMonad (Ref a) readRef :: Ref a -> RefMonad a writeRef :: Ref a -> a -> RefMonad ()

Assuming this is a pure interface, you need one more thing: runRefMonad :: RefMonad a -> a This little function creates a lot of big issues. For example: foo :: (Int, ()) foo = (runRefMonad (readRef ref), comp) where ref = runRefMonad (newRef 42) comp = runRefMonad (writeRef ref 32) What is the value of foo? This issue is solved by the type system trick of Control.Monad.ST, which is essentially the monad you describe. But it is not implemented purely (even though it has a pure interface). If you wanted to do it with a state monad and a Map, you have more problems than just garbage collection. You have to have a heterogeneous map, because different references can hold values of different types. There are three ways I am aware of of making a heterogeneous map: (1) allocating unique keys (requires the map to be in a ST-like existential context to be safe) and storing GHC.Prim.Anys in the map, and unsafeCoercing, relying on the type system to show that the unsafeCoerce is safe. (2) allocating unique keys (w/existential context) and storing Dynamics, then casting. Requires a (Typeable a) constraint on your operations, and is really just as unsafe as above (what do you do when the cast fails?) (3) keeping track of the keys in the type (a la hetero-map on hackage). Incompatible with the standard Monad class, which does not allow the type to change between binds. There may be more, of course. But so far they all seem to involve some sort of trickery. I would be delighted to see a pure, unsafe*-free implementation of your interface. I have never seen one, and I don't really expect it to exist. Likewise I would love to see a proof that it doesn't. Luke