राज्य मोनैड का यह सरल उपयोग क्यों एक ढेर अतिप्रवाह का कारण बनता है?

Question

मैं राज्य मोनड के साथ खेल रहा था, और मुझे नहीं पता कि कोड के इस साधारण टुकड़े में स्टैक ओवरफ़्लो क्या हो रहा है।

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 

नोट मैं सिर्फ पता है कि कोड के इस टुकड़े में समस्या खड़ी कर रहा है चाहते हैं, काम ही नहीं महत्वपूर्ण प्रति है।

Answer 1

समस्या यह है कि Control.Monad.State.Lazy's (>> =) इतनी आलसी है कि यहां तक ​​कि ($!) आपकी मदद नहीं करता है।
नियंत्रण का प्रयास करें। Monad.State.Strict, जो ($!) तक पहुंच जाना चाहिए।

आलसी राज्य मोनैड का (>> =) सभी (मूल्य, राज्य) जोड़ी पर बिल्कुल नहीं देखता है, इसलिए अंत से पहले कुछ मूल्यांकन प्राप्त करने का एकमात्र तरीका fm >>= f में है जोड़ी deconstruct। यह यहां नहीं होता है, इसलिए आपको एक बड़ा थंक मिलता है, जो स्टैक के लिए बहुत बड़ा होता है जब रनस्टेट अंततः परिणाम चाहता है।

ठीक है, मैंने खा लिया है, अब मैं विस्तृत कर सकता हूं। मुझे आलसी State s मोनड की पुरानी (mtl-1.x) परिभाषा का उपयोग करने दें, आंतरिक मोनैड के बिना वहां देखना थोड़ा आसान है। नई (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 (>> =) की परिभाषा const tick है। एक निरंतर कार्य के रूप में, यह निश्चित रूप से इसके तर्क का निरीक्षण करने की आवश्यकता नहीं है। तो tick >> tick हो जाता है जब तक blobN मूल्यांकन किया जाना है

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 छुआ नहीं है। लेकिन इसे बाहरीतम कन्स्ट्रक्टर में मूल्यांकन करने की आवश्यकता है - जोड़ी कन्स्ट्रक्टर (,) - सीईसी को ट्रिगर करने के लिए पर्याप्त होगा और इससे बदले में पूर्ण मूल्यांकन हो जाएगा। अब, million में, runState पहुंचने के बाद अंतिम snd तक किसी भी मूल्यांकन की आवश्यकता नहीं है। उस समय तक, एक लाख परतों के साथ एक थक्का बनाया गया है। उस थकंक का मूल्यांकन करना प्रारंभिक स्थिति तक पहुंचने तक स्टैक पर कई let m' = m+1 in seq m' ((),m') को धक्का देने की आवश्यकता है, और यदि स्टैक उन्हें पकड़ने के लिए काफी बड़ा है, तो उन्हें पॉप किया जाएगा और लागू किया जाएगा। तो यह तीन ट्रैवर्सल होगा, 1. थंक का निर्माण, 2. थैंक से परतों को छीलना और उन्हें ढेर पर धक्का देना, 3. ढेर का उपभोग करना।

Control.Monad.State.Strict की (>> =) बस इतना सख्त प्रत्येक बाँध पर seq रों मजबूर करने के लिए है, इस प्रकार केवल एक ट्रेवर्सल, कोई (nontrivial) 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') के मूल्यांकन की मांग seqs' = s+1 के मूल्यांकन से जुड़ा हुआ है कि द्वारा हो जाता है, सब कुछ पूरी तरह से पर मूल्यांकन किया जाता है प्रत्येक बांध, कोई thunks, कोई ढेर नहीं।

हालांकि, आपको अभी भी सावधान रहना होगा। इस मामले में, seq (resp। ($!)) और शामिल प्रकारों की उथली संरचना के कारण, मूल्यांकन (>>) के आवेदन के साथ रखा गया। आम तौर पर, गहन संरचित प्रकारों और/या बिना seq एस के साथ, सीएमएसस्ट्रेट भी बड़े थंक्स बनाता है जो ढेर ओवरफ्लो का कारण बन सकता है। उन परिस्थितियों में सीएमएसलाज़ी द्वारा उत्पन्न लोगों की तुलना में thunks थोड़ा सा सरल और कम उलझन में हैं।

दूसरी तरफ, सीएमएसलाज़ी की आलस्य अन्य कंप्यूटेशंस की अनुमति देती है जो सीएमएसस्ट्रिक्ट के साथ असंभव हैं। उदाहरण के लिए, सीएमएसलाज़ी बहुत कम मोनैड प्रदान करता है जहां

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

समाप्त हो जाता है। [लेकिन ध्यान रखें कि राज्य तब अनुपयोगी है; इसका उपयोग करने से पहले, इसे पूरी अनंत सूची में यात्रा करना होगा। इसलिए, यदि आप ऐसा कुछ करते हैं, इससे पहले कि आप राज्य-निर्भर कंप्यूशन को फिर से शुरू कर सकें, आपको put एक ताजा राज्य होना चाहिए।]