I think this question is best illustrated with an example.
A type that wraps a non-deterministic function:
data ND a b = N { runN :: a -> [(b, ND a b)] }
instance Show (ND a b) where
show n = show "<ND>"
An example of ND
:
nd :: ND String Int
nd = N $ \a -> case a of
"hello" -> [(length a, nd), (length a + 100, nd)]
"world" -> [(length a + 10, nd)]
_ -> []
remarks: Please note how nd outputs a list of tuples, each tuple containing the result of computation, and a new ND
(actually the same as the original, but let's ignore that for now).
Now construct a process that receives inputs from a source and runs nd for all inputs.
The wrong Process
:
-- | Please note this is wrong, since only the first result of computation is used
toProcess :: ND a b -> Process a b
toProcess = construct . plan where
plan n = do
a <- await
case runN n a of
[] -> stop
((b,n'):xs) -> yield b >> plan n'
remarks: this process above is wrong since only the first result of computation is taken. Ideally, the process should branch into several parallel processes, each one yielding an output b, and recursing with its own version of n'
. The end result should be a list of possible outcomes
Use case:
ret :: [Int]
ret = run $ source ["hello", "world", "again"] ~> toProcess nd
-- Run with toProcess above:
[5,15]
-- But ideally, should yield a list of possible results:
[[5,15],[105,15]]
I believe you need to embed your computations into the
[]
monad, which is a natural way how to model non-deterministic computations. Then you'll haveProcessT []
,PlanT []
etc.: