ざっくりparseして、出力をfilterやheadで加工したかった

fork :: [ParsecT s u [] a] -> ParsecT s u [] a
fork = join . lift

※ list-monadで非決定的計算できるのは、parsecに限った話ではない

ParsecTをlist-monadと合成するだけなので、上のように定義する
型注釈なしならjoin . lift :: (Monad (t m), Monad m, MonadTrans t) => m (t m a) -> t m a

非決定的の厳密な定義を知らないが、chooseとfail1が使えるので非決定的と呼んでいいはず
ただしfail = fork []であって、Prelude.fail(Text.Parsec.parserFail)ではない

例

p = try p' <|> many1 anyChar where
    p' = do
        x <- manyTill anyChar $ char '+'
        fork
            [ return x
            , (x ++) <$> p
            ]

>>> runParserT p () "input" "a+b+c" where
[Right "a",Right "ab",Right "abc"]

q = try q' <|> fork [] where
    q' = do
        x <- p
        fork
            [ return [x]
            , (x :) <$> q
            ]

>>> runParserT p () "input" "a+b+c" where
[Right ["a"],Right ["a","b"],Right ["a","b","c"],Right ["a","bc"],Right ["ab"],Right ["ab","c"],Right ["abc"]]

ここではきものをぬいでくださいのような文をparseするとき便利なんじゃないでしょうか

参考

parsecで非決定的パース

  1. On Lispの説明による ↩