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.