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