Using Data.Machine, how would you describe a plan that branches with results of a non-deterministic function?

Question

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]]

Answer 1

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 have ProcessT [], PlanT [] etc.:

toProcess :: ND a b -> ProcessT [] a b
toProcess = construct . plan where
    plan n = do 
        a <- await
        case runN n a of
            []  -> stop
            xs  -> do
                (b, n') <- lift xs
                yield b
                plan n'

ret :: [[Int]]
ret = runT $ source ["hello", "world", "again"] ~> toProcess nd
-- produces: [[5,15],[105,15]]