How to nondeterministically put a value in a state?

Question

In the following code, how can I replace put 1 with some code that insert nondeterministically 1 or 2 in the state?

import Control.Monad.List
import Control.Monad.Trans.State

test :: StateT Int [] Int
test = do
  put 1
  v <- get
  return v

Answer 1

Your monad stack signature is already the correct one.

Lift a computation from the [] monad and bind to its value. This will fork the computation:

test :: StateT Int [] Int
test = do
  s <- lift [1,2,3]
  put s
  v <- get
  return v

Testing to see it works:

*Main> runStateT test 10
[(1,1),(2,2),(3,3)]

Not only there are many results, but the state gets included in the nondeterminism as well.

If test had had type ListT (State Int) Int, only the results would have been nondetermistic, the state would have been shared among all the branches in the computation:

test :: ListT (State Int) Int
test = do
  s <- ListT $ return [1,2,3]
  put s
  v <- get
  return v

The result:

*Main> runState (runListT test) 10
([1,2,3],3)