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

[wren ng thornton]

Louis Wasserman wrote:
> I follow.  The primary issue, I'm sort of wildly inferring, is that use of
> STT -- despite being pretty much a State monad on the inside -- allows
> access to things like mutable references?

That's exactly the problem. The essential reason for ST's existence are 
STRefs which allow mutability.

With only a single "path of execution"[1] the destructive mutability 
can't be observed (i.e. ST is observationally equivalent to State which 
performs non-destructive updates). However once nondeterminism, 
concurrency (not parallelism), or backtracking enter the picture the 
bisimilarity goes away and it's possible to observe the mutations and 
break referential transparency.


[1] An intentionally vague phrase. Abstractly speaking nondeterminism, 
concurrency, and backtracking all amount to existing simultaneously at 
multiple points in the program with each of these points moving at an 
independent rate. Since they're independent it's possible for one 
"thread" to make a change and then have another move to see it. With 
only a single execution point it's not possible to tell what your 
history is, and so you can't know if it changes out from behind you.


> More serious question: The issue of nondeterministic branching and the State
> monad is something that's occurred to me previously.  Do I understand
> correctly that this would require use of an arrow transformer, rather than a
> monad?

Nope. You can just use StateT over list or Logic[2] and everything works 
out. Since the state of State/StateT is a persistent data structure[3] 
it's fine to hold onto copies of it from many points along it's update 
history. With a nondeterminism monad you essentially just hold onto 
copies of the state at each choice point, thus it's available whenever 
you need to backtrack.


[2] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/logict

[3] Whereas using STRefs or similar would enable creating ephemeral data 
structures more familiar to imperative programmers. By their nature, if 
we wanted to keep copies of these throughout their mutation history, 
then we'd have to clone the data structure so that future mutations 
don't affect the old copy. Or equivalently, use a copy-on-write scheme.

-- 
Live well,
~wren