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 usemplus
andmzero
(or derivedmsum
,mfilter
,guard
etc.) fromMonadPlus
than using list operations directly. If you later change your monad stack, for example from[]
to ourNonDet 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 definetype 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 modifiedtraverse
) would be[("a",Sum {getSum = 2}),("b",Sum {getSum = 2}),("c",Sum {getSum = 1})]