Overnight I had the following thought, which I think could work rather well. The most basic implementation of the idea is as follows:
class MonadST s m | m -> s where liftST :: ST s a -> m a instance MonadST s (ST s) where ... instance MonadST s m => MonadST ... newtype FooT m e = FooT (StateT Foo m e) instance (Monad m, MonadST s m) => Monad (FooT m) where ... instance (Monad m, MonadST s m) => MonadBar (FooT m) where <operations using an ST state> instance (Monad m, MonadST s m) => MonadST s (FooT m) where ... The point here is that a MonadST instance guarantees that the bottom monad is an ST -- and therefore single-threaded of necessity -- and grants any ST-based monad transformers on top of it access to its single state thread. The more fully general approach to guaranteeing an underlying monad is single-threaded would be to create a dummy state parameter version of each single-threaded monad -- State, Writer, and Reader -- and add a typeclass called MonadThreaded or something. The real question with this approach would be how to go about unwrapping ST-based monad transformers in this fashion: I'm thinking that you would essentially perform unwrapping of the outer monad using an ST computation which gets lifted to the next-higher monad. So, say, for example: newtype MonadST s m => ArrayT e m a = ArrayT {execArrayT :: StateT (STArray s Int e) m a} runArrayT :: (Monad m, MonadST s m) => Int -> ArrayT e m a -> m a runArrayT n m = liftST (newArray_ (0, n-1)) >>= evalStateT (execArrayT m) Key points: - A MonadST s m instance should *always* imply that the bottom-level monad is of type ST s, preferably a bottom level provided when defining a monad by stacking transformers. The fact that the bottom monad is in ST should guarantee single-threaded, referentially transparent behavior. - A non-transformer implementation of an ST-bound monad transformer would simply involve setting the bottom monad to ST, rather than Identity as for most monad transformers. - Unwrapping an ST-bound monad transformer involves no universal quantification on the state type. After all transformers have been unwrapped, it should be possible to invoke runST on the final ST s a. - Both normal transformers and ST-bound transformers should propagate MonadST. I'm going to go try implementing this idea in stateful-mtl now... Louis Wasserman wasserman.lo...@gmail.com On Mon, Feb 16, 2009 at 3:07 AM, Sittampalam, Ganesh < ganesh.sittampa...@credit-suisse.com> wrote: > Well, I think a type system like Clean's that had linear/uniqueness types > could "fix" the issue by actually checking that the state is single-threaded > (and thus stop you from applying it to a "forking" monad). But there's a > fundamental operational problem that ST makes destructive updates, so to > support it as a monad transformer in general you'd need a type system that > actually introduced fork operations (which "linear implicit parameters" used > to do in GHC , but they were removed because they were quite complicated > semantically and noone really used them). > > ------------------------------ > *From:* haskell-cafe-boun...@haskell.org [mailto: > haskell-cafe-boun...@haskell.org] *On Behalf Of *Louis Wasserman > *Sent:* 16 February 2009 03:31 > *To:* Dan Doel > *Cc:* Henning Thielemann; haskell-cafe@haskell.org > *Subject:* Re: [Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl > > Okay, I tested it out and the arrow transformer has the same problem. I > realized this after I sent the last message -- the point is that at any > particular point, intuitively there should be exactly one copy of a State# s > for each state thread, and it should never get duplicated; allowing other > monads or arrows to hold a State# s in any form allows them to hold more > than one, violating that goal. > > I'm not entirely convinced yet that there *isn't* some really gorgeous > type system magic to fix this issue, like the type-system magic that > motivates the type of runST in the first place, but that's not an argument > that such magic exists...it's certainly an interesting topic to mull. > > Louis Wasserman > wasserman.lo...@gmail.com > > > On Sun, Feb 15, 2009 at 9:20 PM, Dan Doel <dan.d...@gmail.com> wrote: > >> On Sunday 15 February 2009 9:44:42 pm Louis Wasserman wrote: >> > Hello all, >> > >> > I just uploaded stateful-mtl and pqueue-mtl 1.0.1. The ST monad >> > transformer and array transformer have been removed -- I've convinced >> > myself that a heap transformer backed by an ST array cannot be >> > referentially transparent -- and the heap monad is now available only as >> a >> > basic monad and not a transformer, though it still provides priority >> queue >> > functionality to any of the mtl wrappers around it. stateful-mtl >> retains a >> > MonadST typeclass which is implemented by ST and monad transformers >> around >> > it, allowing computations in the the ST-bound heap monad to perform ST >> > operations in its thread. >> > >> > Since this discussion had largely led to the conclusion that ST can only >> be >> > used as a bottom-level monad, it would be pretty uncool if ST >> computations >> > couldn't be performed in a monad using ST internally because the ST >> thread >> > was hidden and there was no way to place ST computations 'under' the >> outer >> > monad. Anyway, it's essentially just like the MonadIO typeclass, except >> > with a functional dependency on the state type. >> > >> > There was a question I asked that never got answered, and I'm still >> > curious: would an ST *arrow* transformer be valid? Arrows impose >> > sequencing on their operations that monads don't... I'm going to test >> out >> > some ideas, I think. >> >> Your proposed type: >> >> State (Kleisli []) x y = (s, x) -> [(s, y)] >> >> is (roughly) isomorphic to: >> >> x -> StateT s [] y = x -> s -> [(s, y)] >> >> The problem with an ST transformer is that the state parameter needs to be >> used linearly, because that's the only condition under which the >> optimization >> of mutable update is safe. ST ensures this by construction, as opposed to >> other languages (Clean) that have type systems that can express this kind >> of >> constraint directly. However, with STT, whether the state parameter is >> used >> linearly is a function of the wrapped monad. You'd have to give a more >> fleshed >> out version of your proposed state arrow transformer, but off the top of >> my >> head, I'm not sure it'd be any better. >> >> -- Dan >> > > ============================================================================== > Please access the attached hyperlink for an important electronic > communications disclaimer: > http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html > ============================================================================== > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe