[Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl
Dan Doel
dan.doel at gmail.com
Mon Feb 16 16:14:33 EST 2009
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 -}
More information about the Haskell-Cafe
mailing list