But the m -> s dependency will have been removed by the time runST gets a hold of it! It works, I just tested it.<br><br>*Control.Monad.Array.ArrayM> :t runST (runArrayT 5 Nothing getContents)<br>runST (runArrayT 5 Nothing getContents) :: [Maybe a]<br>
*Control.Monad.Array.ArrayM> runST (runArrayT 5 Nothing getContents)<br>[Nothing,Nothing,Nothing,Nothing,Nothing]<br><br>There is, unfortunately, one last key point needed in this approach: the transformer cannot implement MonadTrans, which requires that it work for all monads. The hack I added is<br>
<br>class MonadSTTrans s t where<br> stLift :: MonadST s m => m a -> t m a<br><br>instance MonadTrans t => MonadSTTrans s t where<br> stLift = lift<br><br>which, as a side effect, makes explicit the distinction between normal monad transformers and ST-wrapped monad transformers.<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 10:04 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">I don't think this can be right, because the m -> s
dependency will contradict the universal quantification of s required by runST.
In other words, unwrapping the transformers will leave you with an ST
computation for a specific s, which runST will reject.</font></span></div><br>
<div dir="ltr" align="left" lang="en-us">
<hr>
<font face="Tahoma" size="2"><b>From:</b> Louis Wasserman
[mailto:<a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a>] <br><b>Sent:</b> 16 February 2009
16:01<br><b>To:</b> Sittampalam, Ganesh<br><b>Cc:</b> Dan Doel; Henning
Thielemann; <a href="mailto:haskell-cafe@haskell.org" target="_blank">haskell-cafe@haskell.org</a><div><div></div><div class="Wj3C7c"><br><b>Subject:</b> Re: [Haskell-cafe]
ANNOUNCE: pqueue-mtl, stateful-mtl<br></div></div></font><br></div><div><div></div><div class="Wj3C7c">
<div></div>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" target="_blank">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" target="_blank">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>
<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>
<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>
<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></div>
</blockquote></div><br>