How do you use the list monad to compute/represent the outcome of a non-deterministic computation?

Question

I want to structure a computation where the context is the history of all paths leading the present (which forms a tree), and the function is the present state conditional on the past state. The function itself is non-deterministic so one past state could result in several future states, thus the tree branches. It makes sense to represent the outcome of this computation as a tree, but is there a way to tersely express it with a list monad? Or some other construct that I don't know?

Answer 1

I'd like to add to Tikhon Jelvis's answer that if you need to trace how your executions branch, you could use a more complicated monad stack combination. For example:

import Control.Monad
import Control.Monad.Writer
import Data.Sequence

-- | Represents a non-deterministic computation
-- that allows to trace the execution by sequences of 'w'.
type NonDet w a = WriterT (Seq w) [] a

A value of WriterT (Seq w) [] a is inside [(a, Seq w)], that is, a list of possible outcomes, each holding the result together with a sequence of marks of type w. We use these marks to trace our steps.

We first create a helper function that just adds a mark to the current trace of execution:

-- | Appends a mark to the current trace.
mark :: w -> NonDet w ()
mark = tell . singleton

and perhaps a more convenient function that adds a mark and then proceeds with a given computation:

-- | A helper function appends a mark and proceeds.
(#>) :: w -> NonDet w a -> NonDet w a
(#>) x = (mark x >>)

As a very simple example, let's say we want to traverse a tree

data Tree a = Leaf a | Bin (Tree a) (Tree a)

(In reality, there would be no tree of course, branching would be determined by something sophisticated.)

And we will remember the path we traversed using a sequence of directions

data Direction = L | R
  deriving (Show, Read, Eq, Ord, Enum, Bounded)

Our traversal function would then look like this:

traverse :: Tree a -> NonDet Direction a
traverse (Leaf x)  = return x
traverse (Bin l r) = (L #> traverse l) `mplus` (R #> traverse r)

Calling

runWriterT $ traverse $ Bin (Bin (Leaf "a") (Leaf "b")) (Leaf "c")

produces in

[("a",fromList [L,L]),("b",fromList [L,R]),("c",fromList [R])]

Notes:

• Note the usage of mplus for branching the monadic computation. It is more convenient to use mplus and mzero (or derived msum, mfilter, guard etc.) from MonadPlus than using list operations directly. If you later change your monad stack, for example from [] to our NonDet Direction, your existing code will work without modifications.

• For WriterT we can use any monoid, not just sequences. For example, if all we cared about was the number of steps taken, we could define

  type NonDet a = WriterT (Sum Int) [] a
  
  mark :: NonDet w ()
  mark tell (Sum 1)
  

  Then calling mark would just increment our counter, and the result of calling (slightly modified traverse) would be

  [("a",Sum {getSum = 2}),("b",Sum {getSum = 2}),("c",Sum {getSum = 1})]
  

Answer 2

Using the list monad would let you structure the computation like a tree, but it would lose the source information. At the end, you would have a list of results, but you would not know where each individual result came from.

If this is all you care about, the list monad is perfect. Let's imagine you have a non-deterministic step function:

step :: State -> [State]

if we want to just step it through a bunch of times, we could write something like:

startState >>= step >>= step >>= step

this will give us all the possible results after 3 steps. If we wanted to generalize this to any number, we could write a simple helper function by using the monadic composition operator (<=<) from Control.Monad. This works just like ., except for function of the form a -> m b instead of normal functions (a -> b). It could look something like this:

stepN :: Int -> (State -> [State]) -> State -> [State]
stepN n f = foldr (<=<) return (replicate n f)

Now to get three non-deterministic steps, we can just write stepN 3 step. (You'll probably want to come up with better names for the functions :P.)

In summary: using the list monad, the computation itself is shaped like a tree, but you only get to look at the results at the end. This should be clear from the types involved: at the end, you get a [State], which is by its very nature flat. However, the function State -> [State] branches, so the computation to arrive to the end has to look like a tree.

For things like that, the list type is very convenient to use.

Answer 3

You can actually do even better than the other proposed solutions. You can keep an independent history for each successive branch and trace the execution path in real time.

Here's how you do it using pipes-4.0.0 (currently still on Github):

import Control.Monad.Trans.Class (lift)
import Control.Monad.Trans.State
import Pipes
import qualified Pipes.Prelude as P

branch :: Int -> StateT [Int] (ListT' IO) [Int]
branch n =
    if (n <= 0) then get
    else do
        path <- lift $ P.each [1, 2]
        lift $ lift $ putStrLn $ "Taking path " ++ show path
        modify (path:)
        branch (n - 1)

pipe :: () -> Producer' [Int] IO ()
pipe () = runRespondT (evalStateT (branch 3) [])

main = runProxy $ (pipe >-> P.print) ()

Here's what it outputs:

Taking path 1
Taking path 1
Taking path 1
[1,1,1]
Taking path 2
[2,1,1]
Taking path 2
Taking path 1
[1,2,1]
Taking path 2
[2,2,1]
Taking path 2
Taking path 1
Taking path 1
[1,1,2]
Taking path 2
[2,1,2]
Taking path 2
Taking path 1
[1,2,2]
Taking path 2
[2,2,2]

Normally if you want to save a context of currently visited states you would use:

StateT [node] [] r

... where node is a place you have visited. StateT keeps track of every node you visit, and [] is the non-determinism part. However, if you want to add effects you need to replace [] with the monad transformer equivalent: ListT:

StateT [node] (ListT IO) r

This is how you derive the type of branch. In our particular case the nodes we are visiting are Ints and branch returns the current context at the end of each path that it takes.

When you evalStateT that with an empty initial context you get:

evalStateT (branch 3) [] :: ListT IO [Int]

That's a non-deterministic computation that will try out each branch, tracing the result in IO as it goes along, and then return the local context at the end of the result. There will be 8 final results since our branch is going to take 8 total paths.

If we run that using runRespondT, we get a Producer:

pipe :: () -> Producer' [Int] IO ()

This producer will emit results as it reaches the end of each execution path, tracing as it goes along. We don't have to wait until the end of the computation to see the traces. All we need to view the [Int]s that it is outputting is to hook it up to a Consumer:

P.print :: () -> Consumer [Int] IO r

pipe >-> P.print :: () -> Effect IO ()

This transforms our final computation into an Effect in the base monad (in this case IO). We can run this effect using runProxy:

runProxy $ (pipe >-> P.print) () :: IO ()

This then both traces the computation and prints out the end point of each path.