I just posted stateful-mtl and pqueue-mtl 1.0.2, making use of the new approach to single-threaded ST wrapping. I discovered while making the modifications to both packages that the MonadSTTrans type class was unnecessary, enabling a cleaner integration with mtl proper. I'm pretty confident that this approach is airtight, but let me know if you encounter contradictions or problems.<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:21 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">Oh, I see, every derived monad has to have an 's' in its
type somewhere.</font></span></div><br>
<div dir="ltr" align="left" lang="en-us">
<hr>
<font face="Tahoma" size="2"><div class="Ih2E3d"><b>From:</b> Louis Wasserman
[mailto:<a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a>] <br></div><b>Sent:</b> 16 February 2009
16:17<div><div></div><div class="Wj3C7c"><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><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>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" target="_blank">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" 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">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><br><b>Subject:</b> Re: [Haskell-cafe] ANNOUNCE: pqueue-mtl,
stateful-mtl<br></div></div></font><br></div>
<div>
<div></div>
<div>
<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>
<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>