[Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl

[Sittampalam, Ganesh]

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-bounces at haskell.org
[mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Louis Wasserman
Sent: 16 February 2009 03:31
To: Dan Doel
Cc: Henning Thielemann; haskell-cafe at 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.louis at gmail.com



On Sun, Feb 15, 2009 at 9:20 PM, Dan Doel <dan.doel at 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
==============================================================================
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090216/78f6dc54/attachment.htm