Разве mapM Haskell не ленив?

Ну, есть ленивый, а есть ленивый . mapM действительно ленив в том смысле, что не выполняет больше работы, чем должен.Однако посмотрите на сигнатуру типа:

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

Подумайте, что это означает: вы даете ему функцию a -> m b и набор a s. Обычная карта может превратить их в группу из m b s, но не в m [b] . Единственный способ объединить b в один [b] , не мешая монаде, - это использовать >> = для последовательности mb вместе, чтобы построить список .

Фактически, mapM в точности эквивалентна последовательности . карта .

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

Если вы хотите работать с неограниченной монадической последовательностью, вам потребуется либо явное управление потоком, например, условие завершения цикла, каким-то образом встроенное в цепочку привязок, такие простые рекурсивные функции, как mapM и последовательность не предоставляет - или пошаговая последовательность, что-то вроде этого:

data Stream m a = Nil | Stream a (m (Stream m a))

... так что вы заставляете только столько монадных слоев, сколько необходимо.

Edit :: Что касается splitRandom , то здесь происходит то, что вы передаете ему вычисление Rand , оценивая его с помощью seed splitRandom получает, затем возвращает результат.Без splitRandom начальное число, используемое одиночным getRandom , должно происходить из конечного результата упорядочивания бесконечного списка, поэтому оно зависает. С дополнительным splitRandom , используемому начальному числу нужно только распределять поток через два вызова splitRandom , поэтому он работает. Окончательный список случайных чисел работает, потому что вы покинули монаду Rand в этот момент, и от ее конечного состояния ничего не зависит.

Это попытка доказательства того, что 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 = fa в монаде 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]

мы ожидаем, что последовательность перехватит Nothing и вернет ошибку для всего этого:

sequence mebs = Nothing

Однако для этого списка:

mebs2 = [Just 3, Just 4]

мы ожидаем, что последовательность даст нам:

sequence mebs = Just [3, 4]

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

Примечание: В предыдущей версии этого ответа утверждалось, что foldr вычисляет, начиная с конца списка, и вообще не будет работать с бесконечными списками, но это неверно! Если оператор, который вы передаете в foldr , ленив по своему второму аргументу и выдает вывод с помощью ленивого конструктора данных, такого как список, foldr с радостью будет работать с бесконечным списком. См. Пример foldr (\ x xs -> (дублировать x x) ++ xs) [] [1 ...] . Но это не относится к нашему оператору k .