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

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

Try

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]

после долгого ожидания ожидает spring ожидаемого результата 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

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

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

Ответ 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. С бесконечным списком выражений это невозможно.

Ответ 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

Ответ 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).