Оценка и утечка пространства в Haskell

Я изучаю Haskell и в настоящее время пытаюсь склонить голову к монадам. Во время игры с некоторым генерированием случайных чисел я снова сработал на ленивой оценке. Чтобы упростить что-то близкое к:

roll :: State StdGen Int
roll = do
    gen <- get
    let (n, newGen) = randomR (0,1) gen
    put newGen
    return n

main = do
    gen <- getStdGen
    let x = sum $ evalState (replicateM iterations roll) gen
    print x

в нечто подобное:

roll' :: IO Int
roll' = getStdRandom $ randomR (0,1)

main = do
    x' <- fmap sum $ replicateM iterations roll'
    print x'

на большее число iterations, скажем, 1000 * 1000 * 10, второй пример приводит к переполнению стека.

Почему первая версия с удовольствием работает в постоянном пространстве, а вторая взрывается?

Говоря более широко, вы можете рекомендовать некоторые чтения, чтобы улучшить одну ментальную модель ленивой оценки Хаскелла? (Вводный для промежуточного уровня, желательно.) Поскольку, когда дело доходит до оценки в Haskell, моя интуиция полностью меня терпит.

Ответ 1

Это потому, что Control.Monad.State реэкспортирует Control.Monad.State.Lazy. Если вы импортировали, Control.Monad.State.Strict, оба будут переполняться таким образом.

Причина, по которой он переполняется со строгим State или IO, заключается в том, что replicateM необходимо выполнить действие iterations раз рекурсивно, прежде чем он сможет создать список. Говоря свободно, replicateM должен "комбинировать" "эффекты" всех действий, которые он реплицирует в один гигантский "эффект". Термины "комбинировать" и "эффект" очень расплывчаты и могут означать бесконечное количество разных вещей, но они касаются лучшего, что мы можем сказать о таких абстрактных вещах. replicateM с большим значением закончится переполнением стека почти во всех вариантах монады. Это тот факт, что это не с ленивым State тем странным.

Чтобы понять, почему он не переполняется ленивым State, вам нужно изучить детали (>>=) для lazy State и replicateM. Следующие определения значительно упрощены, но они отражают детали, необходимые для иллюстрации того, как это работает.

newtype State s a = State { runState :: s -> (a, s) }

instance Monad (State s) where
    return x = State $ \s -> (x, s)
    x >>= f = State $ \s -> let (a, s') = runState x s in runState (f a) s'

replicateM :: Monad m => Int -> m a -> m [a]
replicateM 0 _ = return []
replicateM n mx | n < 0 = error "don't do this"
                | otherwise =
                    mx >>= \x -> replicateM (n - 1) mx >>= \xs -> return (x:xs)

Итак, сначала посмотрите replicateM. Обратите внимание, что когда n больше 0, это вызов (>>=). Поэтому поведение replicateM тесно зависит от того, что делает (>>=).

Когда вы смотрите на (>>=), вы видите, что он создает функцию перехода состояния, которая связывает результаты функции перехода состояния x в привязке let, затем возвращает результат функции перехода, что результат f применяется к аргументам из этой привязки.

Хорошо, это утверждение было ясным, как грязь, но это действительно важно. Позвольте просто заглянуть в лямбду на данный момент. Если посмотреть на результат функции (>>=), вы увидите let {something to do with x} in {something to do with f and the results of the let binding}. Это важно при ленивой оценке. Это означает, что, возможно, он может игнорировать x или, может быть, часть его, когда он оценивает (>>=), если это разрешает конкретная функция f. В случае ленивого State это означает, что он может отложить вычисление будущих значений состояния, если f может создать конструктор перед просмотром состояния.

Это оказывается тем, что позволяет ему работать. Конкретный способ replicateM собирает вызовы (>>=), он приводит к функции, которая создает конструкторы (:), прежде чем проверять состояние, переданное им. Это позволяет инкрементную обработку списка, если последнее состояние никогда не проверяется. Если вы когда-либо смотрите на конечное состояние, это разрушает способность функционировать постепенно, потому что конечное состояние требует выполнения всей работы для его вычисления. Но ваше использование evalState привело к тому, что конечное состояние было выброшено без экспертизы, поэтому оценка была бесплатной для постепенного перехода.

Ответ 2

Преступник скрыт глубоко внутри replicateM. Давайте посмотрим на источник.

replicateM        :: (Monad m) => Int -> m a -> m [a]
replicateM n x    = sequence (replicate n x)

sequence       :: Monad m => [m a] -> m [a] 
sequence ms = foldr k (return []) ms where
  k m m' = do { x <- m; xs <- m'; return (x:xs) }

В частности, посмотрите однократное разворачивание foldr в sequence

foldr k (return []) (replicate n roll')

do x  <- roll'
   xs <- foldr k (return []) (replicate n roll')
   return (x:xs)

Другими словами, если мы не сможем лениво вернуться (x : ... thunk ... ) раньше, мы разберем всю репликацию до возвращения первого значения. Ответ на вопрос о том, можем ли мы вернуть эту ценность, имеет отношение к определению (>>=) в нашей монаде.

roll' >>= \x -> foldr k (return []) (replicate n roll') >>= \xs -> return (x:xs)

Справедливости ради следует сказать, что, поскольку IO выполняет побочные эффекты, которые он будет выполнять последовательно связывает - мы определенно собираемся развернуть все это. State имеет две формы: версию Control.Monad.Trans.State.Lazy и версию Control.Monad.Trans.State.Strict, где Control.Monad.Trans.State по умолчанию используется версия Lazy. Там (>>=) определяется как

m >>= k  = StateT $ \s -> do
    ~(a, s') <- runStateT m s
    runStateT (k a) s'

Итак, мы можем видеть явное неопровержимое связывание, которое позволяет нам приступить к возврату результата лениво.

Стоит взглянуть на недавний обзор этой проблемы Joachim Breitner. Там также много работы над этим в экосистемах pipes и conduit, которые, возможно, стоит изучить.

Как правило, стоит подозревать replicateM, однако, из-за этого понятия секвенирования, которое мы видели выше: "постройте голову, затем постройте хвост, затем верните минусы".