उसी स्केल कार्यान्वयन के दौरान हास्केल का फ़ोल्डर स्टैक ओवरफ्लो क्यों नहीं करता है?

Question

मैं FP in Scala पढ़ रहा हूं।

व्यायाम 3.10 कहता है कि foldRight अतिप्रवाह (नीचे दी गई छवियां देखें)। जहां तक ​​मुझे पता है, हालांकि foldr हास्केल में नहीं है।

http://www.haskell.org/haskellwiki/

-- if the list is empty, the result is the initial value z; else 
-- apply f to the first element and the result of folding the rest 
foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty, the result is the initial value; else 
-- we recurse immediately, making the new initial value the result 
-- of combining the old initial value with the first element. 
foldl f z []  = z     
foldl f z (x:xs) = foldl f (f z x) xs 

यह कैसे अलग व्यवहार हो सकता है?

दो अलग-अलग भाषाओं/कंपाइलरों के बीच क्या अंतर है जो इस अलग व्यवहार का कारण बनते हैं?

यह अंतर कहां से आता है? मंच ? भाषा? कंपाइलर?

क्या स्कैला में एक स्टैक-सुरक्षित फ़ोल्ड राइट लिखना संभव है? यदि हां, तो कैसे?

Answer 1

हास्केल आलसी है। परिभाषा

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

हमें बताता है कि एक गैर खाली सूची xs साथ foldr f z xs के व्यवहार आलस्य के संयोजन समारोह f की से निर्धारित होता है। x और thunk -

विशेष रूप से कॉल foldr f z (x:xs) ढेर पर सिर्फ एक thunk आबंटित करता है, {foldr f z xs} (लेखन एक thunk एक अभिव्यक्ति ... आयोजित करने के लिए {...}), और दो तर्क के साथ f कहता है। आगे क्या होता है, f की ज़िम्मेदारी है।

विशेष रूप से, अगर यह एक आलसी डेटा निर्माता है (उदाहरण के लिए (:) की तरह), इसे तुरंत foldr कॉल (निर्माता के दो (संदर्भ के लिए) दो मानों द्वारा भरा स्लॉट के साथ) के फोन करने वाले को लौटा दी जाएगी।

और अगर f अपने मूल्य सही पर, कम से कम संकलक अनुकूलन कोई Thunks सब पर बनाया जाना चाहिए के साथ (या एक, ज्यादा से ज्यादा - वर्तमान एक) की मांग करता है, के रूप में foldr f z xs का मूल्य तुरंत जरूरत है और हमेशा की तरह ढेर के आधार पर मूल्यांकन के लिए इस्तेमाल किया जा सकता है:

foldr f z [a,b,c,....,n] == 
    a `f` (b `f` (c `f` (... (n `f` z)...))) 

तो foldr वास्तव में पैदा कर सकता है तो, जब बहुत देर तक इनपुट सूची पर सख्त संयोजन समारोह के साथ प्रयोग किया।लेकिन यदि संयोजन समारोह दाहिने ओर अपने मूल्य की मांग नहीं करता है, या केवल इसके एक हिस्से की मांग करता है, तो मूल्यांकन को एक थंक में निलंबित कर दिया जाएगा, और f द्वारा बनाए गए आंशिक परिणाम तुरंत लौटा दिए जाएंगे। बाईं ओर तर्क के साथ ही, लेकिन वे इनपुट सूची में संभावित रूप से thunks के रूप में आते हैं।

Answer 2

हास्केल आलसी है। तो foldr ढेर पर आवंटित, ढेर नहीं। तर्क समारोह की कठोरता के आधार पर, यह एक एकल (छोटा) परिणाम, या एक बड़ी संरचना आवंटित कर सकता है।

सख्त, पूंछ-पुनरावर्ती कार्यान्वयन की तुलना में आप अभी भी अंतरिक्ष खो रहे हैं, लेकिन यह स्पष्ट नहीं दिखता है, क्योंकि आपने ढेर के लिए ढेर का व्यापार किया है।

Answer 3

ध्यान दें कि लेखक यहां स्केल मानक लाइब्रेरी में किसी भी फ़ोल्ड राइट परिभाषा का जिक्र नहीं कर रहे हैं, जैसे सूची में परिभाषित एक। वे धारा 3.4 में ऊपर दिए गए फ़ोल्ड राइट की परिभाषा का जिक्र कर रहे हैं।

स्कैला मानक लाइब्रेरी सूची को उलटकर फ़ोल्ड लाइफ के संदर्भ में फ़ोल्ड राइट को परिभाषित करता है (जिसे निरंतर स्टैक स्पेस में किया जा सकता है) फिर पास किए गए फ़ंक्शन के तर्कों के साथ फ़ोल्डलिफ्ट को कॉल करना। इस सूची के लिए काम करता है, लेकिन, एक संरचना जो सुरक्षित रूप से वापस नहीं लिया जा सकता है के लिए काम नहीं करेगा उदाहरण के लिए:

scala> Stream.continually(false) 
res0: scala.collection.immutable.Stream[Boolean] = Stream(false, ?) 

scala> res0.reverse 
java.lang.OutOfMemoryError: GC overhead limit exceeded 

अब देता है क्या इस ऑपरेशन का परिणाम होना चाहिए के बारे में सोचना:

Stream.continually(false).foldRight(true)(_ && _) 

उत्तर गलत होना चाहिए, इससे कोई फर्क नहीं पड़ता कि धारा में कितने झूठे मूल्य हैं या यदि यह अनंत है, तो यदि हम उन्हें संयोजन के साथ जोड़ना चाहते हैं, तो परिणाम गलत होगा। निश्चित रूप से

Haskell कोई समस्या नहीं के साथ इस हो जाता है:

Prelude> foldr (&&) True (repeat False) 
False 

और उस वजह से दो महत्वपूर्ण बातें की है: हास्केल के foldr धारा पार किए जाने की सही करने के लिए छोड़ दिया है, सही करने के लिए नहीं से छोड़ दिया, और हास्केल द्वारा आलसी है चूक। यहां पहला आइटम, वह फ़ोल्डर वास्तव में बाएं से दाएं की सूची को घुमाता है, जो कुछ लोगों को सही से शुरू करने के रूप में सही गुना के बारे में सोचने वाले लोगों को आश्चर्यचकित या भ्रमित कर सकता है, लेकिन सही गुना की महत्वपूर्ण विशेषता यह नहीं है कि यह किस संरचना से शुरू होता है पर, लेकिन किस दिशा में सहयोगीता है। तो [1,2,3,4], एक सूची और एक सेशन op नाम के एक बाईं गुना

((1 op 2) op 3) op 4) 

है और एक सही गुना

(1 op (2 op (3 op 4))) 

है लेकिन मूल्यांकन के आदेश नहीं करना चाहिए देना मामला। तो अध्याय 3 में लेखकों ने यहां क्या किया है, यह आपको एक गुना देना है जो सूची को बाएं से दाएं स्थानांतरित करता है, लेकिन क्योंकि स्कैला डिफ़ॉल्ट रूप से सख्त है, हम अभी भी अनंत झूठी धाराओं को पार करने में सक्षम नहीं होंगे, लेकिन कुछ धैर्य, वे अध्याय 5 में उस पर पहुंच जाएंगे :) मैं आपको एक चुपके की चोटी दूंगा, चलिए फ्लाई राइट के बीच अंतर को देखते हैं क्योंकि इसे मानक पुस्तकालय में परिभाषित किया गया है और इसे स्केलज़ में फोल्डबल टाइपक्लास में परिभाषित किया गया है:

def foldRight[B](z: B)(op: (A, B) => B): B 

यहाँ है scalaz के Foldable से परिभाषा:

यहाँ स्केला मानक पुस्तकालय से कार्यान्वयन है

अंतर यह है कि बी एस सभी आलसी हैं, और अब हम हमारे अनंत धारा फिर से गुना करने के लिए मिलता है, जब तक हम एक समारोह है जो अपनी दूसरा पैरामीटर में पर्याप्त रूप से आलसी है देने के रूप में:

scala> Foldable[Stream].foldRight(Stream.continually(false),true)(_ && _) 
res0: Boolean = false 

Answer 4

एक आसान हास्केल में इसे प्रदर्शित करने का तरीका आलसी मूल्यांकन का प्रदर्शन करने के लिए समीकरण तर्क का उपयोग करना है।चलो foldr के मामले में find समारोह लिखें:

-- Return the first element of the list that satisfies the predicate, or `Nothing`. 
find :: (a -> Bool) -> [a] -> Maybe a 
find p = foldr (step p) Nothing 
    where step pred x next = if pred x then Just x else next 

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

एक उत्सुक भाषा में, यदि आप foldr साथ find ने लिखा कि यह पूरी सूची और उपयोग हे (एन) स्थान को बढ़ावा देते हैं। आलसी मूल्यांकन के साथ, यह पहला तत्व है कि विधेय को संतुष्ट करता है पर बंद हो जाता है, और केवल हे (1) अंतरिक्ष (सापेक्ष कचरा संग्रहण) का उपयोग करता है:

find odd [0..] 
    == foldr (step odd) Nothing [0..] 
    == step odd 0 (foldr (step odd) Nothing [1..]) 
    == if odd 0 then Just 0 else (foldr (step odd) Nothing [1..]) 
    == if False then Just 0 else (foldr (step odd) Nothing [1..]) 
    == foldr (step odd) Nothing [1..] 
    == step odd 1 (foldr (step odd) Nothing [2..]) 
    == if odd 1 then Just 1 else (foldr (step odd) Nothing [2..]) 
    == if True then Just 1 else (foldr (step odd) Nothing [2..]) 
    == Just 1 

यह मूल्यांकन, कदम की एक सीमित संख्या में बंद हो जाता है के बावजूद तथ्य यह है कि सूची [0..] अनंत है, इसलिए हम जानते हैं कि हम पूरी सूची में नहीं जा रहे हैं। इसके अलावा, प्रत्येक चरण में अभिव्यक्ति की जटिलता पर ऊपरी बाध्य है, जो इसका मूल्यांकन करने के लिए आवश्यक स्मृति पर निरंतर ऊपरी सीमा में अनुवाद करता है।

कुंजी यहाँ step समारोह है कि हम साथ तह रहे इस संपत्ति है कि: कोई बात नहीं क्या x और next के मूल्यों या तो, यह:

1. Just x के मूल्यांकन, लागू बिना next थंक, या
2. next थंक कॉल करें (असल में, अगर सचमुच नहीं है)।