Почему функция последовательности Haskell не может быть ленивой или почему рекурсивные монадические функции не могут быть ленивыми

Question

С вопросом " Распечатка всего содержимого каталога по порядку в порядке широты" приводит к низкой эффективности, я понял, что низкая эффективность вызвана странным поведением рекурсивных функций монады.

Пытаться

sequence $ map return [1..]::[[Int]]
sequence $ map return [1..]::Maybe [Int]

и GHCI попадет в бесконечный расчет.

Если переписать функцию последовательности в более читабельном виде, как показано ниже:

sequence' []     = return []
sequence' (m:ms) = do {x<-m; xs<-sequence' ms; return (x:xs)}

и попробовать:

sequence' $ map return [1..]::[[Int]]
sequence' $ map return [1..]::Maybe [Int]

мы получаем ту же ситуацию, бесконечный цикл.

Попробуйте ограниченный список

sequence' $ map return [1..]::Maybe [Int]

это даст ожидаемый результат Just [1,2,3,4..] после долгого ожидания.

Из того, что мы попробовали, мы можем прийти к выводу, что, хотя определение последовательности "кажется ленивым, оно является строгим и должно разбирать все числа, прежде чем результат последовательности" может быть напечатан.

Не только последовательность ", если мы определим функцию

iterateM:: Monad m => (a -> m a) -> a -> m [a]
iterateM f x = (f x) >>= iterateM0 f >>= return.(x:)

и попробовать

iterateM (>>=(+1)) 0

тогда происходит бесконечный расчет.

Как все мы знаем, немонадная итерация определяется точно так же, как и вышеупомянутый iterateM, но почему итерация ленива, а iterateM строг. Как видно из вышеизложенного, iterateM и sequence 'являются рекурсивными монадическими функциями. Есть ли что-то странное в рекурсивных монадических функциях?

Answer 1

Проблема не в определении sequenceЭто операция основной монады. В частности, это строгость монады >>= операция, которая определяет строгость sequence,

Для достаточно ленивой монады вполне возможно запустить sequence в бесконечном списке и потреблять результат постепенно. Рассматривать:

Prelude>  :m + Control.Monad.Identity
Prelude Control.Monad.Identity> runIdentity (sequence $ map return [1..] :: Identity [Int])

и список будет распечатываться (расходоваться) по мере необходимости.

Это может быть полезным, чтобы попробовать это с Control.Monad.State.Strict а также Control.Monad.State.Lazy:

-- will print the list
Prelude Control.Monad.State.Lazy> evalState (sequence $ map return [1..] :: State () [Int]) ()
-- loops
Prelude Control.Monad.State.Strict> evalState (sequence $ map return [1..] :: State () [Int]) ()

в IO монада, >>= по определению является строгим, поскольку эта строгость является именно тем свойством, которое необходимо для обоснования последовательности эффектов. Я думаю, что ответ @jberryman является хорошей демонстрацией того, что подразумевается под >>=". За IO и другие монады со строгим >>=каждое выражение в списке должно быть оценено до sequence может вернуться. С бесконечным списком выражений это невозможно.

Answer 2

Вы не совсем гроклируете механику связывания:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

Вот реализация последовательности, которая работает только для списков с 3 длинами:

sequence3 (ma:mb:mc:[]) = ma >>= (\a-> mb >>= (\b-> mc >>= (\c-> return [a,b,c] )))

Вы видите, как мы должны "запускать" каждое "монадное действие" в списке, прежде чем мы сможем вернуть внешний конструктор (т.е. самые внешние минусы или (:))? Попробуйте реализовать это по-другому, если вы не верите.

Это одна из причин, по которым монады полезны для ввода-вывода: существует неявная последовательность эффектов, когда вы связываете два действия.

Вы также должны быть осторожны при использовании терминов "ленивый" и "строгий". Это правда с sequence что вы должны пройти весь список, прежде чем окончательный результат может быть перенесен, но следующее прекрасно работает:

Prelude Control.Monad> sequence3 [Just undefined, Just undefined, Nothing]
Nothing

Answer 3

Одновалентный sequence вообще не может работать лениво на бесконечных списках. Рассмотрим его подпись:

sequence :: Monad m => [m a] -> m [a]

Он объединяет все монадические эффекты в своем аргументе в один эффект. Если вы примените его к бесконечному списку, вам нужно будет объединить бесконечное количество эффектов в один. Для некоторых монад это возможно, для некоторых монад это не так.

В качестве примера рассмотрим sequence специализируется на Maybe, как вы сделали в своем примере:

sequence :: [Maybe a] -> Maybe [a]

Результат Just ... если все элементы в массиве Just ..., Если какой-либо из элементов Nothing тогда результат Nothing, Это означает, что если вы не изучите все элементы ввода, вы не сможете определить, является ли результат Nothing или же Just ...,

То же самое относится и к sequence специализируется на []: sequence :: [[a]] -> [[a]], Если какой-либо из элементов аргумента является пустым списком, весь результат является пустым списком, как в sequence [[1],[2,3],[],[4]], Итак, чтобы оценить sequence в списке списков вы должны изучить все элементы, чтобы увидеть, как будет выглядеть результат.

---

С другой стороны, последовательность, специализированная на Reader Монада может обработать свой аргумент лениво, потому что на самом деле нет никакого "эффекта" ReaderМонадическое вычисление. Если вы определите

inf :: Reader Int [Int]
inf = sequence $ map return [1..]

или возможно

inf = sequence $ map (\x -> reader (* x)) [1..]

это будет работать лениво, как вы можете видеть, позвонив take 10 (runReader inf 3),