Вот попытка доказать, что mapM return [1..] не заканчивается. Предположим на данный момент, что мы находимся в монаде Identity (аргумент будет применяться и к любой другой монаде):
mapM return [1..] -- initial expression
sequence (map return [1 ..]) -- unfold mapM
let k m m' = m >>= \x ->
m' >>= \xs ->
return (x : xs)
in foldr k (return []) (map return [1..]) -- unfold sequence
Пока все хорошо ...
-- unfold foldr
let k m m' = m >>= \x ->
m' >>= \xs ->
return (x : xs)
go [] = return []
go (y:ys) = k y (go ys)
in go (map return [1..])
-- unfold map so we have enough of a list to pattern-match go:
go (return 1 : map return [2..])
-- unfold go:
k (return 1) (go (map return [2..])
-- unfold k:
(return 1) >>= \x -> go (map return [2..]) >>= \xs -> return (x:xs)
Напомним, что return a = Identity a в монаде Identity и (Identity a) >>= f = f a в монаде Identity. Продолжение:
-- unfold >>= :
(\x -> go (map return [2..]) >>= \xs -> return (x:xs)) 1
-- apply 1 to \x -> ... :
go (map return [2..]) >>= \xs -> return (1:xs)
-- unfold >>= :
(\xs -> return (1:xs)) (go (map return [2..]))
Обратите внимание, что на данный момент мы хотели бы подать заявку на \xs, но пока не можем! Вместо этого мы должны продолжать развертывание, пока у нас не будет значения для применения:
-- unfold map for go:
(\xs -> return (1:xs)) (go (return 2 : map return [3..]))
-- unfold go:
(\xs -> return (1:xs)) (k (return 2) (go (map return [3..])))
-- unfold k:
(\xs -> return (1:xs)) ((return 2) >>= \x2 ->
(go (map return [3..])) >>= \xs2 ->
return (x2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) ((\x2 -> (go (map return [3...])) >>= \xs2 ->
return (x2:xs2)) 2)
На данный момент мы все еще не можем применить к \xs, но мы можем применить к \x2. Продолжение:
-- apply 2 to \x2 :
(\xs -> return (1:xs)) ((go (map return [3...])) >>= \xs2 ->
return (2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) (\xs2 -> return (2:xs2)) (go (map return [3..]))
Теперь мы достигли точки, в которой ни \xs , ни \xs2 еще нельзя уменьшить! Наш единственный выбор:
-- unfold map for go, and so on...
(\xs -> return (1:xs))
(\xs2 -> return (2:xs2))
(go ((return 3) : (map return [4..])))
Итак, вы можете видеть, что из-за foldr мы создаем ряд применимых функций, начиная с конца списка и возвращаясь обратно. Поскольку на каждом этапе список ввода бесконечен, это развертывание никогда не прекратится, и мы никогда не получим ответ.
Это имеет смысл, если вы посмотрите на этот пример (заимствованный из другого потока StackOverflow, я не могу найти какой в данный момент). В следующем списке монад:
mebs = [Just 3, Just 4, Nothing]
мы ожидаем, что sequence поймает Nothing и вернет ошибку в целом:
sequence mebs = Nothing
Однако для этого списка:
mebs2 = [Just 3, Just 4]
мы ожидаем, что последовательность даст нам:
sequence mebs = Just [3, 4]
Другими словами, sequence имеет , чтобы увидеть весь список монадических вычислений, связать их воедино и запустить их все, чтобы найти правильный ответ. sequence не может дать ответ, не видя весь список.
Примечание: Предыдущая версия этого ответа утверждала, что foldr вычисляется, начиная с конца списка, и не будет работать вообще для бесконечных списков, но это неверно! Если оператор, который вы передаете в foldr, ленив во втором аргументе и производит вывод с помощью ленивого конструктора данных, такого как список, foldr будет успешно работать с бесконечным списком. См. foldr (\x xs -> (replicate x x) ++ xs) [] [1...] для примера. Но дело обстоит не так с нашим оператором k.