Tại sao việc sử dụng đơn giản trạng thái đơn nguyên này lại gây ra tình trạng tràn ngăn xếp?

Question

Tôi đang chơi với các đơn vị nhà nước, và tôi không biết điều gì gây ra tràn ngăn xếp trong đoạn mã đơn giản này.

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 

Note Tôi chỉ muốn biết những gì đang gây ra vấn đề trong đoạn mã này, nhiệm vụ chính nó là không quan trọng cho mỗi gia nhập.

Answer 1

Vấn đề là Control.Monad.State.Lazy's (>> =) quá lười đến nỗi ngay cả ($!) Cũng không giúp được bạn.
Hãy thử Control.Monad.State.Strict, điều đó sẽ đạt đến ($!).

(> =) của đơn vị trạng thái lười không nhìn vào tất cả ở cặp giá trị, vì vậy cách duy nhất để thực hiện một số đánh giá trước khi kết thúc đạt được f trong m >>= f deconstruct cặp. Điều đó không xảy ra ở đây, vì vậy bạn nhận được một lượng lớn, đó là quá lớn cho ngăn xếp khi runState cuối cùng muốn có kết quả.

Được rồi, tôi đã ăn, bây giờ tôi có thể xây dựng. Hãy để tôi sử dụng định nghĩa cũ (mtl-1.x) của mẫu đơn State s lười biếng, có thể dễ dàng thấy ở đó nếu không có đơn nguyên bên trong. Định nghĩa mới (mtl-2.x) type State s = StateT s Identity hoạt động giống nhau, nó chỉ là viết và đọc nhiều hơn. Định nghĩa của (>> =) là

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

Bây giờ, let bindings là lười biếng, vì thế đây là

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

chỉ dễ đọc hơn

. Vì vậy, (>> =) cho phép các blob hoàn toàn không được đánh giá. Chỉ cần đánh giá nếu k cần kiểm tra fst blob để xác định cách tiếp tục hoặc k a cần kiểm tra snd blob.

Trong replicateM r tick, các phép tính được ghép với (>>), do đó, định nghĩa của k trong (>> =) là const tick. Là một hàm liên tục, nó chắc chắn không nhất thiết phải kiểm tra đối số của nó. Vì vậy, tick >> tick trở thành

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 

các seq không được đụng đến blobN phải được đánh giá. Nhưng cần phải đánh giá nó cho các nhà xây dựng ngoài cùng - nhà xây dựng cặp (,) - sẽ là đủ để kích hoạt seq và điều đó sẽ lần lượt dẫn đến đánh giá đầy đủ ở đây. Bây giờ, trong million, không có gì yêu cầu bất kỳ đánh giá nào cho đến khi snd cuối cùng sau khi đạt được runState. Vào thời điểm đó, một thunk với một triệu lớp đã được xây dựng. Đánh giá rằng thunk đòi hỏi đẩy nhiều let m' = m+1 in seq m' ((),m') trên stack cho đến khi đạt được trạng thái ban đầu, và nếu ngăn xếp là đủ lớn để giữ chúng, sau đó họ sẽ được popped và áp dụng. Vì vậy, nó sẽ là ba traversals, 1. xây dựng thunk, 2. lột lớp từ thunk và đẩy chúng trên stack, 3. tiêu thụ stack.

(>> =) của Control.Monad.State.Strict chỉ đủ nghiêm ngặt để buộc seq s trên mỗi liên kết, do đó, chỉ có một chuyển đổi, không có (nontrivial) thunk được xây dựng và tính toán chạy trong hằng số không gian. Định nghĩa là

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

Sự khác biệt quan trọng là mô hình kết hợp trong case biểu là nghiêm ngặt, ở đây blob phải được đánh giá để các nhà xây dựng ngoài cùng để phù hợp với nó chống lại các mô hình trong case.
Với m = tick = State (\m -> let m' = m+1 in seq m' ((),m')) phần thiết yếu trở nên

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

Các mô hình trận đấu đòi hỏi việc đánh giá ((), s') [đến (,) constructor], bởi seq được gắn với việc đánh giá s' = s+1, tất cả mọi thứ là hoàn toàn đánh giá trên mỗi liên kết, không có khối, không có ngăn xếp.

Tuy nhiên, bạn vẫn cần phải cẩn thận. Trong trường hợp này, do seq (resp. ($!)) và cấu trúc nông của các loại có liên quan, đánh giá được cập nhật với ứng dụng (>>). Nói chung, với các loại có cấu trúc sâu hơn và/hoặc không có seq s, C.M.S.Strict cũng xây dựng các khối lớn có thể dẫn đến tràn ngăn xếp. Các mảnh chỉ là một chút đơn giản và ít vướng víu hơn những người được tạo ra bởi C.M.S.Lazy trong những trường hợp đó.

Mặt khác, sự lười biếng của C.M.S.Lazy cho phép các tính toán khác không thể với C.M.S.Strict. Ví dụ: C.M.S.Lazy cung cấp một trong số rất ít monads, trong đó

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

chấm dứt. [Nhưng lưu ý rằng trạng thái sau đó không sử dụng được; trước khi nó có thể được sử dụng, nó sẽ phải đi qua toàn bộ danh sách vô hạn. Vì vậy, nếu bạn làm điều tương tự, trước khi bạn có thể tiếp tục tính toán nhà nước, bạn phải put trạng thái mới.]