<!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=929102016-16022009><FONT face=Arial
color=#800000 size=2>Oh, I see, every derived monad has to have an 's' in its
type somewhere.</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:17<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>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="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>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 lang=en-us dir=ltr align=left>
<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="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>
<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="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>>
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><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>