Используя Data.Machine, как бы вы описали план с ответами на недетерминированные функции?

Question

Я думаю, что этот вопрос лучше всего иллюстрировать на примере.

Тип, который оборачивает недетерминированную функцию:

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

Answer 1

Я считаю, что вам нужно встроить свои вычисления в [] монада, которая является естественным способом моделирования недетерминированных вычислений. Тогда у вас будет 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]]