How can I build a nondeterministic state monad in Haskell?
haskell, non-deterministic, state-monad
Solution
A simple `State` monad is defined as:
data State s a = State (s -> (a, s))
This represents a self-contained and deterministic stateful computation. Considering `[]` as a non-determinism monad, you can have `[State s a]` which represents a non-deterministic set of deterministic computations, or `State s [a]` which represents a deterministic computation producing a non-deterministic set of values. In neither case is any non-determinism present in the structure of the stateful computation itself.
To actually combine the state and non-determinism behaviors in the way you seem to want, you need to combine the two in a way that isn't possible using just `State`; this is the purpose of monad transformers. The type `StateT s [] a` is equivalent to:
data NonDetState s a = NonDetState (s -> [(a, s)])
What this gives you is non-determinism in the state value with only individual choices observable at any one point in the computation.
What this does not allow is any interaction between branches; state changes made in one branch will never be visible from other branches, which is what is generally desired in a non-deterministic computation.
Problem
I want to build a nondeterministic state monad in Haskell. This will allow me to generate all the elements in my search space using the built up state to prune bad locations. Suppose I have the following (pseudo-)code: ``` primitives :: [State Int Element] primitives = [... list of primitive stateful elements ...] combine :: Element -> Element -> State Int Element expand :: Depth -> [State Int Element] expand 0 = primitives expand d = do ... do something to the state ... left <- expand (d-1) right <- expand (d-1) let out = combine left right guard ( ... some check on out ... ) return out ``` There are several things here that don't work: the most basic thing that I need to understand is how to do something to state and then pipe it in to each of the `expand` branches. I've tried a bunch of ways with functions of type `State Int [ State Int Element]` but, ultimately, once I wrap the branches of the list monad in a state wrapper I can't remove it, right? So is there a way to do this? Thanks.