सिलवटों और ढेर के बारे में प्रश्न overflows

Question

आप जानें हास्केल को foldl क्योंकि foldl अतिप्रवाह ढेर की संभावना है एक विकल्प के रूप foldl' के बारे में बात करती है।

• एलवाईएएच के अनुसार, foldl (+) 0 (replicate 1000000 1) को ओवरफ्लो ढेर करना चाहिए, लेकिन यह मेरी मशीन पर नहीं है। क्यों नहीं? भले ही मैं उस संख्या को 10 मिलियन तक बढ़ा दूं, यह अतिप्रवाह नहीं है। यह तब तक बहुत मेमोरी लेता है जब तक कि मेरा ओएस एक्स कंप्यूटर अनुपयोगी न हो और मुझे इसे रीबूट करना होगा।
• foldl' के बजाय मुझे किस मामले में foldl का उपयोग करना चाहिए? मेरे अनुभव में foldl' "बस काम करता है" जबकि foldl अनिवार्य रूप से मेरे कंप्यूटर को क्रैश कर सकता है (ऊपर देखें)।
• मुझे समझ में नहीं आता कि foldr के लिए कुछ भी क्यों नहीं है। foldr स्टैक ओवरफ़्लो क्यों नहीं हो सकता है और foldr' क्यों नहीं है?

Answer 1

यह स्टैक ओवरफ़्लो के साथ क्रैश नहीं होता है क्योंकि स्टैक डिफ़ॉल्ट रूप से अनंत है। यही है, डिफ़ॉल्ट जीएचसी रनटाइम व्यवहार स्टैक को अनिश्चित काल तक बढ़ने की अनुमति देना है - कोई सीमा नहीं है जो स्टैक ओवरफ़्लो त्रुटि को ट्रिगर कर सकती है।

थ्रेड के ढेर (मुख्य थ्रेड के ढेर सहित) ढेर पर रहते हैं:

https://ghc.haskell.org/trac/ghc/ticket/8189

यहाँ एक वर्णन यह कैसे काम करता है। स्टैक बढ़ता है, नए स्टैक भाग आवश्यकतानुसार जोड़े जाते हैं; यदि स्टैक दोबारा घटता है, तो इन अतिरिक्त स्टैक हिस्सों को कचरा कलेक्टर द्वारा पुनः दावा किया जाता है। डिफ़ॉल्ट प्रारंभिक स्टैक आकार जानबूझकर छोटा है, में थ्रेड सृजन के लिए समय और स्थान ओवरहेड को न्यूनतम रखने के लिए, और इसे छोटे कार्य के टुकड़ों के लिए धागे को बढ़ाने के लिए व्यावहारिक बनाने के लिए व्यावहारिक रूप से छोटा है।

Answer 2

क्यों ढेर अतिप्रवाह foldr नहीं कर सकते हैं और यही कारण है कि वहाँ कोई foldr है '?

खैर, foldr नहीं पूंछ पुनरावर्ती है, यानी यह सीधे ही पर फोन नहीं करता है:

foldr f a (x:xs) = f x (foldr f a xs) 

foldr के बाद कम हो जाता है, नियंत्रण करने के लिए गुजरता उपयोगकर्ता द्वारा प्रदान की f। इसलिए, foldr' रखने की कोई आवश्यकता नहीं है जो उन्हें f पर जाने से पहले तर्कों को मजबूर करता है: यदि वह चाहता है, तो कॉलर केवल सख्त f (उदाहरण के लिए बैंग पैटर्न या seq का शोषण कर सकता है)।

चाहे यह ढेर ओवरफ्लो करता है, f पर निर्भर करता है। उदाहरण के लिए,

f x y = x 

सूची को केवल अपने पहले तत्व में एक्सेस किया जाएगा। इसके विपरीत,

f x y = seq y x 

एक स्टैक ओवरफ़्लो (या स्मृति-गहन व्यवहार) का कारण बन सकता है।इसके बजाय,

f x y = x+1 : y 

किसी भी बुरा आश्चर्य के बिना, map (+1) xs का कारण होगा उत्पादन सूची lazily का उत्पादन किया जाना, इसी तरह।

@dfeuer बताते हैं, Data.Foldable.foldr' मौजूद है जो किसी भी Foldable पर सख्त दाएं गुना के रूप में कार्य करता है। सूचियों पर, जैसा कि ऊपर चर्चा की गई है, यह काफी अनावश्यक है। अन्य Foldable प्रकारों पर, यह इसके बजाय सार्थक हो सकता है।