<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2900.3492" name=GENERATOR></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=208460216-16022009><FONT face=Arial 
color=#800000 size=2>I don't think this can be right, because the m -&gt; 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 class=OutlookMessageHeader lang=en-us dir=ltr align=left>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> Louis Wasserman 
[mailto:wasserman.louis@gmail.com] <BR><B>Sent:</B> 16 February 2009 
16:01<BR><B>To:</B> Sittampalam, Ganesh<BR><B>Cc:</B> Dan Doel; Henning 
Thielemann; haskell-cafe@haskell.org<BR><B>Subject:</B> Re: [Haskell-cafe] 
ANNOUNCE: pqueue-mtl, stateful-mtl<BR></FONT><BR></DIV>
<DIV></DIV>Overnight I had the following thought, which I think could work 
rather well.&nbsp; The most basic implementation of the idea is as 
follows:<BR><BR>class MonadST s m | m -&gt; s where<BR>
<DIV style="MARGIN-LEFT: 40px">liftST :: ST s a -&gt; m a<BR></DIV><BR>instance 
MonadST s (ST s) where ...<BR>instance MonadST s m =&gt; MonadST 
...<BR><BR>newtype FooT m e = FooT (StateT Foo m e)<BR><BR>instance (Monad m, 
MonadST s m) =&gt; Monad (FooT m) where ...<BR><BR>instance (Monad m, MonadST s 
m) =&gt; MonadBar (FooT m) where<BR>
<DIV style="MARGIN-LEFT: 40px">&lt;operations using an ST 
state&gt;<BR></DIV><BR>instance (Monad m, MonadST s m)&nbsp; =&gt; 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.&nbsp; 
So, say, for example:<BR><BR>newtype MonadST s m =&gt; ArrayT e m a = ArrayT 
{execArrayT :: StateT (STArray s Int e) m a}<BR><BR>runArrayT :: (Monad m, 
MonadST s m) =&gt; Int -&gt; ArrayT e m a -&gt; m a<BR>runArrayT n m = liftST 
(newArray_ (0, n-1)) &gt;&gt;= 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.&nbsp; 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.&nbsp; 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>&lt;<A 
href="mailto:ganesh.sittampalam@credit-suisse.com">ganesh.sittampalam@credit-suisse.com</A>&gt;</SPAN> 
wrote:<BR>
<BLOCKQUOTE class=gmail_quote 
style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid">
  <DIV>
  <DIV dir=ltr align=left><SPAN><FONT face=Arial color=#800000 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 lang=en-us dir=ltr align=left>
  <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.&nbsp; 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>&lt;<A href="mailto:dan.doel@gmail.com" 
  target=_blank>dan.doel@gmail.com</A>&gt;</SPAN> wrote:<BR>
  <BLOCKQUOTE class=gmail_quote 
  style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid">
    <DIV>On Sunday 15 February 2009 9:44:42 pm Louis Wasserman wrote:<BR>&gt; 
    Hello all,<BR>&gt;<BR>&gt; I just uploaded stateful-mtl and pqueue-mtl 
    1.0.1. &nbsp;The ST monad<BR>&gt; transformer and array transformer have 
    been removed -- I've convinced<BR>&gt; myself that a heap transformer backed 
    by an ST array cannot be<BR>&gt; referentially transparent -- and the heap 
    monad is now available only as a<BR>&gt; basic monad and not a transformer, 
    though it still provides priority queue<BR>&gt; functionality to any of the 
    mtl wrappers around it. &nbsp;stateful-mtl retains a<BR>&gt; MonadST 
    typeclass which is implemented by ST and monad transformers around<BR>&gt; 
    it, allowing computations in the the ST-bound heap monad to perform 
    ST<BR>&gt; operations in its thread.<BR>&gt;<BR>&gt; Since this discussion 
    had largely led to the conclusion that ST can only be<BR>&gt; used as a 
    bottom-level monad, it would be pretty uncool if ST computations<BR>&gt; 
    couldn't be performed in a monad using ST internally because the ST 
    thread<BR>&gt; was hidden and there was no way to place ST computations 
    'under' the outer<BR>&gt; monad. &nbsp;Anyway, it's essentially just like 
    the MonadIO typeclass, except<BR>&gt; with a functional dependency on the 
    state type.<BR>&gt;<BR>&gt; There was a question I asked that never got 
    answered, and I'm still<BR>&gt; curious: would an ST *arrow* transformer be 
    valid? &nbsp;Arrows impose<BR>&gt; sequencing on their operations that 
    monads don't... &nbsp;I'm going to test out<BR>&gt; some ideas, I 
    think.<BR><BR></DIV>Your proposed type:<BR><BR>&nbsp;State (Kleisli []) x y 
    = (s, x) -&gt; [(s, y)]<BR><BR>is (roughly) isomorphic to:<BR><BR>&nbsp;x 
    -&gt; StateT s [] y = x -&gt; s -&gt; [(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>
<P><pre wrap>==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer: 

http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
==============================================================================
</pre></P></BODY></HTML>