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

計算をモナドに埋め込む必要があると思います[]。これは、非決定論的計算をモデル化する自然な方法です。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 に答える