स्पेस लीक, और राइटर्स, और सैम्स (ओह माय!)

Question

मैं हाल ही में राइटर मोनाड के साथ खेल रहा हूं, और मैंने में स्थानांतरित किया है जो एक अंतरिक्ष रिसाव प्रतीत होता है। मैं नहीं कह सकता कि मैं इन चीजों को अभी तक पूरी तरह से समझता हूं, इसलिए मैं जानना चाहता हूं कि यहां क्या हो रहा है, और इसे कैसे ठीक किया जाए।

सबसे पहले, यहाँ कैसे मैं इससे यह त्रुटि उत्पन्न कर सकते हैं:

import Control.Monad.Writer 
import Data.Monoid 

foo :: Integer -> Writer (Sum Integer) Integer 
foo 0 = return 0 
foo x = tell (Sum x) >> foo (pred x) 

main = print $ runWriter $ foo 1000000 

मैं:

Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 

इस बेहतर ढंग से समझने के लिए, मैं लेखक या योग के बिना इसी तरह की सुविधा reimplemented किया है, और अगर मैं चीजें अच्छी और आलसी रखता हूं, मुझे समान त्रुटि मिलती है:

bar :: Integer -> (Integer, Integer) 
bar x = bar' 0 x 
    where bar' c 0 = (0, c) 
      bar' c x = bar' (c + x) (pred x) 

,210

लेकिन मैं समीकरण को seq जोड़कर इस उपाय कर सकते हैं:

bar' c x = c `seq` bar' (c + x) (pred x) 

मैं अपने foo समारोह के seq ing विभिन्न बिट्स की कोशिश की है, लेकिन वह प्रतीत नहीं होता है मदद करने के लिए। इसके अलावा, मैंने Control.Monad.Writer.Strict का उपयोग करने का प्रयास किया है, लेकिन कोई फर्क नहीं पड़ता है।

क्या Sum किसी भी तरह सख्त होने की आवश्यकता है? या क्या मुझे कुछ अलग है?

नोट्स

• मैं गलत यहाँ मेरी शब्दावली हो सकता है। Space leak zoo के अनुसार, मेरी समस्या को 'स्टैक ओवरफ़्लो' के रूप में वर्गीकृत किया जाएगा, और यदि यह मामला है, तो मैं foo को और अधिक पुनरावृत्ति शैली में कैसे परिवर्तित करूं? क्या मेरा मैनुअल समस्या का पुनरावृत्ति है?
• Haskell Space Overflow पढ़ने के बाद, मेरे पास -O2 के साथ संकलित करने का विचार था, बस यह देखने के लिए कि क्या होता है। यह के लिए एक अन्य प्रश्न हो सकता है, लेकिन अनुकूलन के साथ, यहां तक ​​कि मेरे seq 'डी bar फ़ंक्शन चलाने में विफल रहता है। अद्यतन: यदि मैं -fno-full-laziness जोड़ता हूं तो यह समस्या दूर हो जाती है। सख्त लेखक इकाई के लिए स्रोत पर

Answer 1

लेखक इकाई के साथ समस्या यह है कि यह

>>= नहीं पूंछ पुनरावर्ती है:

instance (Monoid w, Monad m) => Monad (WriterT w m) where 
m >>= k = WriterT $ do 
    (a, w) <- runWriterT m 
    (b, w') <- runWriterT (k a) 
    return (b, w `mappend` w') 

आप देख सकते हैं यह दोनों m और k amappend जिसका मतलब है कि पुनरावर्ती कॉल की पूरी ढेर है मूल्यांकन करने के लिए मूल्यांकन करने के लिए है पहले mappend से पहले मजबूर होना चाहिए मूल्यांकन किया जा सकता है। मेरा मानना ​​है कि सख्तता के बावजूद लेखक मोनैड आपकी परिभाषा में ढेर ओवरफ्लो का कारण बनता है (या इसे किसी भी तरह आलसी संस्करण से बचा जा सकता है?)।

यदि आप अभी भी मोनैड का उपयोग करना चाहते हैं तो आप State का प्रयास कर सकते हैं जो पूंछ-पुनरावर्ती है। सख्त put साथ इसके बारे में या तो सख्त संस्करण:

import Control.Monad.State.Strict 

foo :: Integer -> State (Sum Integer) Integer 
foo 0 = return 0 
foo x = do 
    w <- get 
    put $! w `mappend` (Sum x) 
    foo (pred x) 

main = print $ (`execState` Sum 0) $ foo 1000000 

या निरंतरता गुजर शैली (सीपीएस) के साथ आलसी संस्करण:

import Control.Monad.Cont 
import Control.Monad.State.Lazy 

foo :: Integer -> ContT Integer (State (Sum Integer)) Integer 
foo 0 = return 0 
foo x = do 
    w <- get 
    put $! w `mappend` (Sum x) 
    foo (pred x) 

main = print $ ((`execState`Sum 0) . (`runContT`return)) $ foo 1000000 

हैंडी अनुरूप tell के लिए:

stell :: (MonadState w m, Monoid w) => w -> m() 
stell a = get >>= \w -> put $! w `mappend` a 

मुझे लगता है कि यदि संदेह Writer के साथ उपयोग करना संभव था सीपीएस हमें Writer के साथ भी मदद करेगा, लेकिन ऐसा लगता है कि यह पी नहीं है define ContT for MonadWriter के लिए ossible:

Answer 2

देखो: http://hackage.haskell.org/packages/archive/transformers/0.2.2.0/doc/html/src/Control-Monad-Trans-Writer-Strict.html#line-122

आलसी लेखक से अंतर यह है कि बाद में, पैटर्न मैचों आलसी हैं - लेकिन न तो मामले में mappend ऑपरेशन या है इस प्रकार लेखक के "राज्य" को अब तक मजबूर किया गया है। अपनी समस्या को हल करने के लिए, आपको एक "सुपर-सख्त" लेखक की आवश्यकता होगी।

Answer 3

मुझे लगता है कि आपकी समझ सही है।हालांकि संबंधित कार्यों जब अनुकूलन के साथ संकलित

bar :: Integer -> (Integer, Integer) 
bar x = bar' 0 x 
    where bar' c 0 = (0, c) 
      bar' c x = c `seq` bar' (c + x) (pred x) 
     -- bar' c x = let c' = c+x in c' `seq` bar' c' (pred x) 
     -- bar' !c !x = bar' (c+x) (pred x) 

एक ढेर अतिप्रवाह पैदा करता है,:

bar2 :: Integer -> (Integer, Integer) 
bar2 x = bar' 0 x 
    where bar' c 0 = (0, c) 
      bar' !c !x = let c' = c+x in c' `seq` bar' c' (pred x) 

bar3 :: Integer -> Integer 
bar3 x = bar' 0 x 
    where bar' c 0 = c 
      bar' c x = c `seq` bar' (c + x) (pred x) 

bar4 :: Integer -> (Integer, Integer) 
bar4 x = (0, bar' 0 x) 
    where bar' c 0 = c 
      bar' c x = c `seq` bar' (c + x) (pred x) 

नहीं

मैं कैसे इन कार्यों में दिलचस्पी रखता हूँ।

मुझे लगता है कि यह जीएचसी के अनुकूलक में एक बग की तरह दिखता है, और आपको report it होना चाहिए। कोर को देखने से (-ddump-simpl के साथ उत्पादित), c तर्क बहने वाले कार्यों के लिए सभी मामलों में कड़ाई से मूल्यांकन नहीं किया जाता है। bar2 मूल में मिला सबसे नज़दीकी कामकाजी संस्करण है, और यह मुझे अधिक निर्दिष्ट लगता है।

चूंकि आपके पास एक बहुत ही सरल परीक्षण केस है, इसलिए यह एक अच्छा मौका तय होगा।