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">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">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 class="Ih2E3d">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>