How can I build a nondeterministic state monad in Haskell?

Question

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.

Answer 1

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.