Кон Монад ломает лень в Хаскелле

Я пытался Монаду Конта и обнаружил следующую проблему.

  • Сначала создайте бесконечный список и поднимите все элементы в монаду Cont.
  • Используйте операцию последовательности, чтобы получить монаду Cont в бесконечном списке.
  • Когда мы пытаемся запустить монаду, например, с головой, она попадает в бесконечный цикл пытаясь расширить продолжение, и голова никогда не называется.

Код выглядит следующим образом:

let inff = map (return :: a -> Cont r a) [0..]
let seqf = sequence inff
runCont seqf head

Итак, это ограничение реализации монады Cont в Haskell? Если да, то как это улучшить?

Ответы

Ответ 1

Причина в том, что даже если значение элемента head sequence someList зависит только от первого элемента someList, эффект sequence someList обычно зависит от всех эффектов someList (и это для большинства монадов). Поэтому, если мы хотим оценить элемент head, нам все равно нужно оценить все эффекты.

Например, если у нас есть список значений Maybe, результат sequence someList равен Just, только если все элементы someList равны Just. Поэтому, если мы попробуем sequence бесконечный список, нам нужно будет изучить его бесконечное количество элементов, если они все Just.

То же самое относится к Cont. В продолжении монады мы можем сбежать в любое время из вычисления и вернуть результат, отличный от того, что было вычислено до сих пор. Рассмотрим следующий пример:

test :: (Num a, Enum a) => a
test = flip runCont head $
    callCC $ \esc -> do
        sequence (map return [0..100] ++ [esc [-1]])

или непосредственно используя Cont вместо callCC:

test' :: (Num a, Enum a) => a
test' = flip runCont head $
            sequence (map return [0..100] ++ [cont (const (-1))])

Результат test равен -1. После обработки первых 100 элементов последний элемент может решить избежать всего этого и вернуть -1. Поэтому, чтобы узнать, что является элементом head sequence someList в Cont, нам снова нужно вычислить их все.

Ответ 2

Это не ошибка с монадой Cont так же, как sequence. Вы можете получить похожие результаты для Either, например:

import Control.Monad.Instances ()

xs :: [Either a Int]
xs = map Right [0..]  -- Note: return = Right, for Either

ys :: Either a [Int]
ys = sequence xs

Вы не можете получить любые элементы ys, пока не вычислит весь список, что никогда не произойдет.

Также обратите внимание: sequence (map f xs) = mapM f xs, поэтому мы можем упростить этот пример:

>>> import Control.Monad.Instances
>>> mapM Right [0..]
<Hangs forever>

Есть несколько монад, где mapM будет работать с бесконечным списком значений, в частности, с ленивой монадией StateT и Identity, но они являются исключением из правила.

Как правило, mapM/sequence/replicateM (без конечных подчеркиваний) являются анти-шаблонами, и правильным решением является использование pipes, что позволяет создавать эффективные потоки, которые не пытаются вычислить все результаты впереди. В начале учебника pipes описывается, как решить это более подробно, но общее правило заключается в том, что каждый раз, когда вы пишете что-то вроде

example1 = mapM f xs

example2 = sequence xs

Вы можете преобразовать его в ленивый Producer, просто преобразуя его в:

example1' = each xs >-> Pipes.Prelude.mapM f

example2' = each xs >-> Pipes.Prelude.sequence

Используя приведенный выше пример с Either, вы должны написать:

>>> import Pipes
>>> let xs = each [0..] >-> mapM Right :: Producer Int (Either a) ()

Затем вы можете лениво обрабатывать поток без генерации всех элементов:

>>> Pipes.Prelude.any (> 10) xs
Right True