But the m -> s dependency will have been removed by the time runST gets a hold of it! It works, I just tested it.
*Control.Monad.Array.ArrayM> :t runST (runArrayT 5 Nothing getContents) runST (runArrayT 5 Nothing getContents) :: [Maybe a] *Control.Monad.Array.ArrayM> runST (runArrayT 5 Nothing getContents) [Nothing,Nothing,Nothing,Nothing,Nothing] 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 class MonadSTTrans s t where stLift :: MonadST s m => m a -> t m a instance MonadTrans t => MonadSTTrans s t where stLift = lift which, as a side effect, makes explicit the distinction between normal monad transformers and ST-wrapped monad transformers. Louis Wasserman wasserman.lo...@gmail.com On Mon, Feb 16, 2009 at 10:04 AM, Sittampalam, Ganesh < ganesh.sittampa...@credit-suisse.com> wrote: > 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. > > ------------------------------ > *From:* Louis Wasserman [mailto:wasserman.lo...@gmail.com] > *Sent:* 16 February 2009 16:01 > *To:* Sittampalam, Ganesh > *Cc:* Dan Doel; Henning Thielemann; haskell-cafe@haskell.org > > *Subject:* Re: [Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl > > Overnight I had the following thought, which I think could work rather > well. The most basic implementation of the idea is as follows: > > class MonadST s m | m -> s where > liftST :: ST s a -> m a > > instance MonadST s (ST s) where ... > instance MonadST s m => MonadST ... > > newtype FooT m e = FooT (StateT Foo m e) > > instance (Monad m, MonadST s m) => Monad (FooT m) where ... > > instance (Monad m, MonadST s m) => MonadBar (FooT m) where > <operations using an ST state> > > instance (Monad m, MonadST s m) => MonadST s (FooT m) where ... > > 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. > > 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. > > 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: > > newtype MonadST s m => ArrayT e m a = ArrayT {execArrayT :: StateT (STArray > s Int e) m a} > > runArrayT :: (Monad m, MonadST s m) => Int -> ArrayT e m a -> m a > runArrayT n m = liftST (newArray_ (0, n-1)) >>= evalStateT (execArrayT m) > > Key points: > - A MonadST s m instance should *always* 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. > - 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. > - 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. > - Both normal transformers and ST-bound transformers should propagate > MonadST. > > I'm going to go try implementing this idea in stateful-mtl now... > > Louis Wasserman > wasserman.lo...@gmail.com > > > On Mon, Feb 16, 2009 at 3:07 AM, Sittampalam, Ganesh < > ganesh.sittampa...@credit-suisse.com> wrote: > >> 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). >> >> ------------------------------ >> *From:* haskell-cafe-boun...@haskell.org [mailto: >> haskell-cafe-boun...@haskell.org] *On Behalf Of *Louis Wasserman >> *Sent:* 16 February 2009 03:31 >> *To:* Dan Doel >> *Cc:* Henning Thielemann; haskell-cafe@haskell.org >> *Subject:* Re: [Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl >> >> 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. >> >> I'm not entirely convinced yet that there *isn't* 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. >> >> Louis Wasserman >> wasserman.lo...@gmail.com >> >> >> On Sun, Feb 15, 2009 at 9:20 PM, Dan Doel <dan.d...@gmail.com> wrote: >> >>> On Sunday 15 February 2009 9:44:42 pm Louis Wasserman wrote: >>> > Hello all, >>> > >>> > I just uploaded stateful-mtl and pqueue-mtl 1.0.1. The ST monad >>> > transformer and array transformer have been removed -- I've convinced >>> > myself that a heap transformer backed by an ST array cannot be >>> > referentially transparent -- and the heap monad is now available only >>> as a >>> > basic monad and not a transformer, though it still provides priority >>> queue >>> > functionality to any of the mtl wrappers around it. stateful-mtl >>> retains a >>> > MonadST typeclass which is implemented by ST and monad transformers >>> around >>> > it, allowing computations in the the ST-bound heap monad to perform ST >>> > operations in its thread. >>> > >>> > Since this discussion had largely led to the conclusion that ST can >>> only be >>> > used as a bottom-level monad, it would be pretty uncool if ST >>> computations >>> > couldn't be performed in a monad using ST internally because the ST >>> thread >>> > was hidden and there was no way to place ST computations 'under' the >>> outer >>> > monad. Anyway, it's essentially just like the MonadIO typeclass, >>> except >>> > with a functional dependency on the state type. >>> > >>> > There was a question I asked that never got answered, and I'm still >>> > curious: would an ST *arrow* transformer be valid? Arrows impose >>> > sequencing on their operations that monads don't... I'm going to test >>> out >>> > some ideas, I think. >>> >>> Your proposed type: >>> >>> State (Kleisli []) x y = (s, x) -> [(s, y)] >>> >>> is (roughly) isomorphic to: >>> >>> x -> StateT s [] y = x -> s -> [(s, y)] >>> >>> The problem with an ST transformer is that the state parameter needs to >>> be >>> used linearly, because that's the only condition under which the >>> optimization >>> of mutable update is safe. ST ensures this by construction, as opposed to >>> other languages (Clean) that have type systems that can express this kind >>> of >>> constraint directly. However, with STT, whether the state parameter is >>> used >>> linearly is a function of the wrapped monad. You'd have to give a more >>> fleshed >>> out version of your proposed state arrow transformer, but off the top of >>> my >>> head, I'm not sure it'd be any better. >>> >>> -- Dan >>> >> >> >> ============================================================================== >> Please access the attached hyperlink for an important electronic >> communications disclaimer: >> http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html >> ============================================================================== >> >> > ============================================================================== > Please access the attached hyperlink for an important electronic > communications disclaimer: > http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html > ============================================================================== > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe