Проводите попытку доказать, что 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 a) >>= f = f a
в Монастыре идентичности. Продолжение:
-- 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
.
Но это не объясняет, почему предыдущая строка с splitRandom решает проблему.Также обратите внимание, что splitRandom фактически разбивает случайное семя на два и использует один из них для создания бесконечного списка, поэтому там не должно быть зависимостей. – qrest
@qrest: Добавлено дополнительное примечание - это помогает? –
@camccann: Нет, это не так. Вот мои рассуждения. Мне нужно использовать одно семя для создания бесконечного списка. Следовательно, я разделил семя и использовал его в «splitRandom $ sequence $ repeat $ getRandom». ПРИМЕЧАНИЕ. Это монодичное выражение, и оно не оценивалось полностью! Обратите внимание, что я целенаправленно получил случайное число для «a» ПОСЛЕ бесконечного списка, доказывая, что семена не зависят. И монашеская монада не использует семя, если не генерируется случайное число, поэтому не должно существовать зависимость от семян. Итак, «вернуть» тот, который фактически заставляет оценивать? – qrest