Implementing RefMonads in Haskell without ST,IO
Tim Sweeney
Derek Elkins
"Tim Sweeney" <t...@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.
_______________________________________________
Haskell mailing list
Has...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Tim Sweeney
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
Hal Daume III
> types simultaneously?
...you could use Dynamics...
but other than that, I think you're stuck...
Derek Elkins
"Tim Sweeney" <t...@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.
Tomasz Zielonka
On Fri, May 30, 2003 at 12:00:26AM -0500, Tim Sweeney wrote:
> Hi Derek,
>
> How can one implement RefMonad below directly in Haskell?
>
> 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.
Typing is one problem. The second problem is with Garbage Collection.
In the straightforward implementation individual references are not
collected - either the whole heap is collected or nothing at all.
Regards,
Tom
--
.signature: Too many levels of symbolic links
Josef Svenningsson
There was an email about this some time ago which discussed this problem
for the special case of the ST-monad:
http://www.haskell.org/pipermail/haskell/2001-September/007922.html
What I really would like to see is a proof that such refmonads cannot be
encoded in pure Haskell.
Cheers,
/Josef
Ashley Yakeley
"Tim Sweeney" <t...@epicgames.com> wrote:
> class Monad m => RefMonad m r | m -> r where
> newRef :: a -> m (r a)
> readRef :: r a -> m a
> writeRef :: r a -> a -> m ()
>
> Is it possible to actually implement a working instance of RefMonad in
> Haskell, without making use of a built-in monad like IO or ST? If so, I'd
> love any tips -- I've been making good use of monads for a while, but can't
> figure this one out.
You certainly wouldn't be able to do this for any monad M which had:
performM :: forall a. M a -> a;
...because it wouldn't be type-safe: you'd be able to construct coerce
:: a -> b just as you can with unsafePerformIO.
--
Ashley Yakeley, Seattle WA