choosing one of the nondeterministic choices

Question

The following toy example computes nondeterministically a number by calling a function anyFunction, and then keeps only the even choices. How could I write a similar code that keeps the maximum choice instead the even choices? Do I need a different monad stack signature?

anyFunction :: StateT Int [] Int
anyFunction = undefined


test :: StateT Int [] Int
test = do
  s <- anyFunction
  put s
  v <- get
  if even v then return v else mzero

Answer 1

What you want is to "run the [] under the StateT" so to speak, obtaining all the Int results of anyFunction, while preserving the rest of the monad stack as much as possible.

You would like a function with a type similar to StateT Int [] Int -> State Int [Int]. That gets all the Ints so that you can calculate the maximum.

But given your monad stack, your function is difficult to implement. Each branching path of the computation has its own "thread" of state, but when you reduce a StateT Int [] Int to a State Int [Int], which "thread" of state should we keep? There's no solution that looks natural.

Now, imagine that you are working with a ListT (State Int) Int monad stack instead. Here all branches share the same "thread" of state. Specializing runListT, it has the signature ListT (State Int) Int -> State Int [Int].

The example could be written as follows:

anyFunction :: ListT (State Int) Int
anyFunction = undefined

test :: ListT (State Int) Int
test = do
  -- preserve non-ListT parts of the stack
  -- and re-wrap the result into a list
  s <- ListT $ liftM (\l -> [maximum l]) $ runListT anyFunction
  put s
  v <- get
  if even v then return v else mzero