Hi Derek, How can one implement RefMonad below directly in Haskell? class Monad m => RefMonad m r | m -> r where newRef :: a -> m (r a) readRef :: r a -> m a writeRef :: r a -> a -> m () I've been able to implement a monad that encapsulates "references to integers", by creating a monad that passes "the heap" (a function int->int, from heap indices to integer values stored in the heap) in and out of functions. That was pretty straightforward, and the monad makes everything look like an imperative language that supports updatable references to integers (and only integers). But how can one implement RefMonad to support references of all possible types simultaneously? The problem is that "readRef" needs to return elements of an arbitrary type, so it has to be able to extract them from some sort of "heap" function or data structure. But what does the heap data structure look like? The values that "readRef :: r a -> m a" depend on type "a", and I can't figure out how to implement that, because "a" is local to that declaration. If this were implemented in C++, for example, the heap could just store "objects", and readRef could cast the object to the appropriate type when returning it. But in Haskell, I don't see any way to do this. -Tim ----- Original Message ----- From: "Derek Elkins" <ddarius@hotpop.com> To: "Tim Sweeney" <tim@epicgames.com> Cc: <haskell@haskell.org> Sent: Thursday, May 29, 2003 10:31 PM Subject: Re: Implementing RefMonads in Haskell without ST,IO

On Thu, 29 May 2003 22:48:05 -0500 "Tim Sweeney" <tim@epicgames.com> wrote:

...

If it's not possible to implement a typesafe RefMonad instance directly in Haskell, without making use of built-in imperative features like IO, then doesn't this refute the claims that monads implement imperative features functionally?

-Tim

You certainly can have an instance of RefMonad that -simulates- updateable references. You can't implement this with update inplace without an update inplace primitive and if Haskell had an update inplace primitive that you could use anywhere it wouldn't be a pure language. Monads in Haskell -allow- imperative features and use of imperative features without breaking the purity of the entire language. Outside a monadic computation equational reasoning always holds, even when talking about imperative actions. That monads implement an imperative effect doesn't mean they implement it the same way an imperative language would. Of course, the actual implementation doesn't matter so implementing it imperatively is just as good as implementing it functionally as far as static semantics go, which is why everything (IO&ST) works out.

On Fri, 30 May 2003 00:00:26 -0500 "Tim Sweeney" <tim@epicgames.com> wrote:

Hi Derek,

How can one implement RefMonad below directly in Haskell?

class Monad m => RefMonad m r | m -> r where newRef :: a -> m (r a) readRef :: r a -> m a writeRef :: r a -> a -> m ()

I've been able to implement a monad that encapsulates "references to integers", by creating a monad that passes "the heap" (a function int->int, from heap indices to integer values stored in the heap) in and out of functions. That was pretty straightforward, and the monad makes everything look like an imperative language that supports updatable references to integers (and only integers).

But how can one implement RefMonad to support references of all possible types simultaneously?

There isn't without an unsafe coerce function. However, you can get all the types that are an instances of a class, e.g. Typeable. As Hal Daume said, you can use Dynamics. GHC's implementation does use an unsafeCoerce function but "A Lightweight Implementation of Generics and Dynamics" (or something very close to that) shows that such a function is unnecessary and only existential quantification is needed to make Dynamics. If you want to be able to change the type you store in/at a reference then this is your only real option. However, likely you want typed references. Dynamics seems unnecessary/overkill for this (though it may be). You know what type you want, you aren't going to mistake it, so you shouldn't need to carry around a TypeRep. Anyways, you may want to check out "A Lightweight Implementation...", it has some interesting type stuff that may give you ideas.