[Haskell-cafe] Reference monad

[Luke Palmer]

On Fri, Mar 11, 2011 at 8:18 PM, Joshua Ball <sciolizer at gmail.com> 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