[Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl

[Dan Doel]

On Monday 16 February 2009 8:44:21 am Josef Svenningsson wrote:
> On Mon, Feb 16, 2009 at 2:30 AM, wren ng thornton <wren at freegeek.org> wrote:
> > Louis Wasserman wrote:
> >> I follow.  The primary issue, I'm sort of wildly inferring, is that use
> >> of STT -- despite being pretty much a State monad on the inside --
> >> allows access to things like mutable references?
> >
> > That's exactly the problem. The essential reason for ST's existence are
> > STRefs which allow mutability.
>
> I'd like to point out one other thing that ST provides, which is often
> forgotten. It provides *polymorphic* references. That is, we can
> create new references of any type.
>
> So ST is a really magical beast. Not only does it provide mutation, it
> also provides mutable references. And these are two different
> features. Now, everyone agrees that mutation is not something that you
> can implement in a functional language, so ST cannot be implemented in
> Haskell for that reason. It has to be given as a primitive. But what
> about polymorphic references? Can they be implemented in Haskell? The
> Claessen conjecture (after Koen Claessen) is that they cannot be
> implemented in Haskell. See the following email for more details:
> http://www.haskell.org/pipermail/haskell/2001-September/007922.html
>
> One could try and separate mutation and polymorphic references and
> give them as two different primitives and implement ST on top of that.
> But I haven't seen anyone actually trying that (or needing it for that
> matter).

There are a couple approximations you can make for polymorphic references. For 
one, you can encode the types of all the references you've made so far in the 
type of the monad, so you get a type like:

    ST r vec1 vec2 a

where vec1 is the types of references coming in, and vec2 is the same going 
out. For instance:

    newSTRef :: ST r vec1 (t ::: vec2) (STRef r t)

Or something of that sort. I've fooled with something like this, and it works 
somewhat, but the obvious problem is that how many and what type of references 
you use has to be statically known, which isn't true for ST.

Someone already mentioned using Dynamic as an alternate base (for instance, 
use a Map of dynamics for underlying storage). Of course, the implementation 
of Dynamic in GHC uses unsafeCoerce, just like ST, so you may not count that. 
However, using GADTs, you can implement Dynamic safely for a closed universe 
of types. So you could create a polymorphic reference monad for whatever such 
universe you wished. Further, if you actually had open GADTs, you could 
actually add the relevant type-rep constructor for every type you declared. 
For instance, jhc's implementation of type classes internally uses such a 
GADT, so one could theoretically make a safe Dynamic, and thus a safe 
polymorphic reference monad.

-- Dan

P.S. Here's some code:

{-# LANGUAGE GeneralizedNewtypeDeriving, Rank2Types #-}

module ST where

import Control.Monad.State

import Data.Dynamic
import Data.Maybe

import qualified Data.IntMap as I

newtype ST r a = ST { unST :: State (I.IntMap Dynamic,Int) a } deriving Monad

newtype STRef r t = STR Int

newSTRef :: Typeable t => t -> ST r (STRef r t)
newSTRef v = ST $ do (m, i) <- get
                     put (I.insert i (toDyn v) m, i+1)
                     return (STR i)

modifySTRef :: Typeable t => STRef r t -> t -> ST r ()
modifySTRef (STR j) v = ST $ do (m, i) <- get
                                put (I.insert j (toDyn v) m, i)
                                return ()

readSTRef :: Typeable t => STRef r t -> ST r t
readSTRef (STR j) = ST $ do (m, i) <- get
                            return . fromJust . fromDynamic $ m I.! j

runST :: (forall r. ST r a) -> a
runST st = evalState (unST st) (I.empty, 0)

test v f = runST (do r <- newSTRef v
                     modifySTRef r (f v)
                     readSTRef r)

{- test 1 (+1) ==> 2 -}