[Haskell-cafe] ANNOUNCE: pqueue-mtl, stateful-mtl
wren ng thornton
wren at freegeek.org
Sun Feb 15 20:30:58 EST 2009
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" 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.
 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
Nope. You can just use StateT over list or Logic and everything works
out. Since the state of State/StateT is a persistent data structure
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.
 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.
More information about the Haskell-Cafe