Overnight I had the following thought, which I think could work rather well. The most basic implementation of the idea is as follows:<br><br>class MonadST s m | m -> s where<br><div style="margin-left: 40px;">liftST :: ST s a -> m a<br>
</div><br>instance MonadST s (ST s) where ...<br>instance MonadST s m => MonadST ...<br><br>newtype FooT m e = FooT (StateT Foo m e)<br><br>instance (Monad m, MonadST s m) => Monad (FooT m) where ...<br><br>instance (Monad m, MonadST s m) => MonadBar (FooT m) where<br>
<div style="margin-left: 40px;"><operations using an ST state><br></div><br>instance (Monad m, MonadST s m) => MonadST s (FooT m) where ...<br><br>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.<br>
<br>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.<br>
<br>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:<br>
<br>newtype MonadST s m => ArrayT e m a = ArrayT {execArrayT :: StateT (STArray s Int e) m a}<br><br>runArrayT :: (Monad m, MonadST s m) => Int -> ArrayT e m a -> m a<br>runArrayT n m = liftST (newArray_ (0, n-1)) >>= evalStateT (execArrayT m)<br>
<br>Key points: <br>- A MonadST s m instance should <i>always</i> 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.<br>
- 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.<br>- 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.<br>
- Both normal transformers and ST-bound transformers should propagate MonadST.<br><br>I'm going to go try implementing this idea in stateful-mtl now...<br><br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br>
<br><br><div class="gmail_quote">On Mon, Feb 16, 2009 at 3:07 AM, Sittampalam, Ganesh <span dir="ltr"><<a href="mailto:ganesh.sittampalam@credit-suisse.com">ganesh.sittampalam@credit-suisse.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div>
<div dir="ltr" align="left"><span><font color="#800000" face="Arial" size="2">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).</font></span></div><br>
<div dir="ltr" align="left" lang="en-us">
<hr>
<font face="Tahoma" size="2"><b>From:</b> <a href="mailto:haskell-cafe-bounces@haskell.org" target="_blank">haskell-cafe-bounces@haskell.org</a>
[mailto:<a href="mailto:haskell-cafe-bounces@haskell.org" target="_blank">haskell-cafe-bounces@haskell.org</a>] <b>On Behalf Of </b>Louis
Wasserman<br><b>Sent:</b> 16 February 2009 03:31<br><b>To:</b> Dan
Doel<br><b>Cc:</b> Henning Thielemann;
<a href="mailto:haskell-cafe@haskell.org" target="_blank">haskell-cafe@haskell.org</a><br><b>Subject:</b> Re: [Haskell-cafe] ANNOUNCE:
pqueue-mtl, stateful-mtl<br></font><br></div><div><div></div><div class="Wj3C7c">
<div></div>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.<br><br>I'm not entirely convinced yet that there
<i>isn't</i> 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.<br><br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a><br><br><br>
<div class="gmail_quote">On Sun, Feb 15, 2009 at 9:20 PM, Dan Doel <span dir="ltr"><<a href="mailto:dan.doel@gmail.com" target="_blank">dan.doel@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div>On Sunday 15 February 2009 9:44:42 pm Louis Wasserman
wrote:<br>> Hello all,<br>><br>> I just uploaded stateful-mtl and
pqueue-mtl 1.0.1. The ST monad<br>> transformer and array transformer
have been removed -- I've convinced<br>> myself that a heap transformer
backed by an ST array cannot be<br>> referentially transparent -- and the
heap monad is now available only as a<br>> basic monad and not a
transformer, though it still provides priority queue<br>> functionality to
any of the mtl wrappers around it. stateful-mtl retains a<br>>
MonadST typeclass which is implemented by ST and monad transformers
around<br>> it, allowing computations in the the ST-bound heap monad to
perform ST<br>> operations in its thread.<br>><br>> Since this
discussion had largely led to the conclusion that ST can only be<br>> used
as a bottom-level monad, it would be pretty uncool if ST computations<br>>
couldn't be performed in a monad using ST internally because the ST
thread<br>> was hidden and there was no way to place ST computations
'under' the outer<br>> monad. Anyway, it's essentially just like the
MonadIO typeclass, except<br>> with a functional dependency on the state
type.<br>><br>> There was a question I asked that never got answered,
and I'm still<br>> curious: would an ST *arrow* transformer be valid?
Arrows impose<br>> sequencing on their operations that monads
don't... I'm going to test out<br>> some ideas, I
think.<br><br></div>Your proposed type:<br><br> State (Kleisli []) x y =
(s, x) -> [(s, y)]<br><br>is (roughly) isomorphic to:<br><br> x ->
StateT s [] y = x -> s -> [(s, y)]<br><br>The problem with an ST
transformer is that the state parameter needs to be<br>used linearly, because
that's the only condition under which the optimization<br>of mutable update is
safe. ST ensures this by construction, as opposed to<br>other languages
(Clean) that have type systems that can express this kind of<br>constraint
directly. However, with STT, whether the state parameter is used<br>linearly
is a function of the wrapped monad. You'd have to give a more fleshed<br>out
version of your proposed state arrow transformer, but off the top of
my<br>head, I'm not sure it'd be any better.<br><font color="#888888"><br>--
Dan<br></font></blockquote></div><br>
</div></div><div class="Ih2E3d"><p></p><pre>==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer:
<a href="http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html" target="_blank">http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html</a>
==============================================================================
</pre></div></div>
</blockquote></div><br>