Я играл с государственной монадой, и я не знаю, что вызывает переполнение стека в этой простой части кода.
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
Примечание Я просто хотел бы знать, что вызывает проблему в этом фрагменте кода, сама задача не важна сама по себе.
Проблема в том, что Control.Monad.State.Lazy( → =) настолько ленив, что даже ($!) вам не помогает.
Попробуйте Control.Monad.State.Strict, который должен достигнуть ($!).
( → =) монадии ленивого состояния вообще не смотрит на пару (значение, состояние), поэтому единственный способ получить некоторую оценку, сделанную до конца, - это иметь f в m >>= f деконструировать пару. Этого не происходит здесь, поэтому вы получаете огромный thunk, который слишком велик для стека, когда 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)
только более читаемый. Таким образом, ( → =) позволяет блоблю полностью не оцениваться. Оценка требуется только в том случае, если k необходимо проверить fst blob, чтобы определить, как продолжить, или k a необходимо проверить snd blob.
В replicateM r tick, вычисления связаны цепью ( → ), поэтому определение k in ( → =) 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 для каждого связывания, таким образом, существует только один обход, нет (нетривиальный) thunk и вычисление выполняется в константе пространство.
Определение
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 s, C.M.S.Strict также создает большие трюки, которые могут привести к переполнению стека. Тонки немного проще и менее запутаны, чем те, что были созданы C.M.S.Lazy в этих обстоятельствах.
С другой стороны, лень C.M.S.Lazy допускает другие вычисления, которые невозможны с C.M.S.Strict. Например, C.M.S.Lazy предоставляет одну из немногих монад, где
take 100 <$> mapM_ something [1 .. ]
завершает работу. [Но имейте в виду, что государство тогда непригодно; прежде чем его можно будет использовать, ему придется путешествовать по всему бесконечному списку. Итак, если вы сделаете что-то подобное, прежде чем вы сможете возобновить вычисления, зависящие от состояния, вы должны put обновить состояние.]