Почему это простое использование монады State вызывает переполнение стека? - PullRequest
Новая
       13

Почему это простое использование монады State вызывает переполнение стека?

17 голосов
/ 03 ноября 2011

Я играл с монадой State, и я не знаю, что вызывает переполнение стека в этом простом куске кода. 

import Control.Monad.State.Lazy

tick :: State Int Int
tick = do n <- get
         put $! (n+1)
         return n

million :: Int
million = snd $ runState (mapM_ (const tick) [1..1000000]) 0

main = print million

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

1 Ответ

41 голосов
/ 03 ноября 2011

Проблема в том, что Control.Monad.State.Lazy (>> =) настолько ленив, что даже ($!) Вам не поможет.
Попробуйте Control.Monad.State.Strict, который должен достичь($!).

(>> =) монады ленивых состояний вообще не смотрит на пару (значение, состояние), поэтому единственный способ выполнить некоторую оценку до концадостигается, что f в m >>= f деконструирует пару.Этого здесь не происходит, так что вы получаете огромный толчок, который слишком велик для стека, когда runState наконец хочет получить результат.

Хорошо, я поел, теперь я могу уточнить.Позвольте мне использовать старое (mtl-1.x) определение ленивой State s монады, там немного легче увидеть без внутренней монады.Новое (mtl-2.x) определение type State s = StateT s Identity ведет себя так же, оно просто больше пишет и читает.Определение (>> =) было 

m >>= k  = State $ \s -> let
    (a, s') = runState m s
    in runState (k a) s'

Теперь привязки let являются ленивыми, поэтому это 

m >>= k = State $ \s -> let
    blob = runState m s
    in runState (k $ fst blob) (snd blob)

только более читабельно.Таким образом, (>> =) позволяет BLOB-объекту полностью оценить.Оценка требуется только в том случае, если k необходимо проверить fst blob, чтобы определить, как продолжить, или k a необходимо проверить snd blob.

В replicateM r tick вычисления вычисляются с помощью (>>), поэтому определение k в (>> =) - const tick.Как постоянная функция, ей определенно не нужно проверять свой аргумент.Таким образом, tick >> tick становится 

State $ \s -> 
    let blob1 = (\n -> let n' = n+1 in seq n' ((),n')) s
        blob2 = (\m -> let m' = m+1 in seq m' ((),m')) (snd blob1)
    in blob2

seq не затрагивается до тех пор, пока blobN не будет оценено.Но необходимости вычислить его для самого внешнего конструктора - парного конструктора (,) - было бы достаточно для запуска seq, и это, в свою очередь, привело бы к полной оценке здесь.Теперь, в million, ничто не требует какой-либо оценки, пока не будет получен окончательный snd после достижения runState.К тому времени был построен ствол с миллионом слоев.Для оценки этого thunk требуется помещать множество let m' = m+1 in seq m' ((),m') в стек до тех пор, пока не будет достигнуто начальное состояние, и, если стек достаточно велик для их хранения, они затем будут извлечены и применены.Таким образом, это будет три обхода: 1. создание thunk, 2. отслоение слоев от thunk и помещение их в стек, 3. использование стека.

(>> =) Control.Monad.State.Strict достаточно строг, чтобы заставить seq s на каждом связывании, таким образом, существует только один обход, нет (нетривиального) блока, и вычисление выполняется в постоянном пространстве.Определение: 

m >>= k = State $ \s ->
    case runState m s of
      (a, s') -> runState (k a) s'

Важным отличием является то, что сопоставление с образцом в выражениях case является строгим, здесь blob должен быть вычислен до самого внешнего конструктора, чтобы сопоставить его с образцом в case.
При m = tick = State (\m -> let m' = m+1 in seq m' ((),m')) существенная часть становится 

case let s' = s+1 in seq s' ((),s') of
    (a, s'') -> runState (k a) s''

Сопоставление с шаблоном требует вычисления ((), s') [для (,) конструктора], с помощью seq, который связанчто касается оценки s' = s+1, то при каждом связывании все оценивается полностью, ни блоков, ни стека.

Однако вам все же нужно быть осторожным.В этом случае, из-за seq (соответственно ($!)) и мелкой структуры участвующих типов, оценка продолжалась с применением (>>).В общем, с более глубокими структурированными типами и / или без seq с, CMSStrict также создает большие блоки, которые могут привести к переполнению стека.Thunks просто немного проще и менее запутан, чем генерируемые CMSLazy в этих обстоятельствах.

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

take 100 <$> mapM_ something [1 .. ]

заканчивается.[Но знайте, что государство тогда непригодно;прежде чем его можно будет использовать, ему придется пройти через весь бесконечный список.Итак, если вы делаете что-то подобное, прежде чем вы сможете возобновить вычисления, зависящие от состояния, вам нужно put новое состояние.]

...