3

我认为这个问题最好用一个例子来说明。

包装非确定性函数的类型：

data ND a b = N { runN :: a -> [(b, ND a b)] }

instance Show (ND a b) where
    show n = show "<ND>"

一个例子ND：

nd :: ND String Int
nd = N $ \a -> case a of 
    "hello" -> [(length a, nd), (length a + 100, nd)]
    "world" -> [(length a + 10, nd)]
    _       -> []

备注：请注意 nd 如何输出一个元组列表，每个元组包含计算结果和一个新的ND（实际上与原始相同，但我们暂时忽略它）。

现在构建一个从源接收输入并为所有输入运行 nd 的进程。

错误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'

备注：上面这个过程是错误的，因为只取了第一个计算结果。理想情况下，该过程应分支为多个并行过程，每个过程产生一个输出 b，并使用其自己的版本递归n'。最终结果应该是可能结果的列表

用例：

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

1 回答 1

2

我相信您需要将计算嵌入到[]monad 中，这是对非确定性计算进行建模的一种自然方式。然后你会有ProcessT []，PlanT []等等：

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]]
于 2013-07-11T07:35:36.093 回答