उत्पाद क्यों नहीं [0 ..] 0 "तत्काल" का मूल्यांकन करता है?

Question

मैं आलस्य को समझने की कोशिश कर रहा हूं। चूंकि 0 किसी भी संख्या के साथ गुणा 0 है, product [0..] 0 का मूल्यांकन नहीं करना चाहिए? मैं भी foldl (*) 1 [0..] की कोशिश की, और के रूप में एक 0 पाया जाता है

myProduct 0 _ = 0 
myProduct _ 0 = 0 
myProduct a b = a*b 

क्यों गुना के रूप में जल्द ही बंद नहीं करता है के रूप में अपने खुद के उत्पाद को परिभाषित करने के?

Answer 1

क्योंकि गुणा करने वाले ऑपरेटर को यह नहीं पता है कि यह जंजीर हो रहा है, और गुना फ़ंक्शन किसी भी तर्क के लिए गुणा ऑपरेटर के विशेष व्यवहार को नहीं जानता है। उस संयोजन के साथ, इसे फोल्ड को खत्म करने के लिए सूची को निकालना होगा। असल में, इस कारण से foldl अनंत सूचियों पर बिल्कुल काम नहीं करता है। foldr करता है, क्योंकि यह सूची के शीर्ष से फ़ंक्शन का विस्तार कर सकता है।

foldl (*) 1 [0..] -> (((..(((1*0)*1)*2)*3....)*inf 

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

foldr (*) 1 [0..] -> 0*(1*(2*(3*((...((inf*1)))...))) 

foldr मामले में सबसे बाहरी गुणा तुरंत पाया जाता है, क्योंकि सूची के बाकी तथ्य एक आलसी thunk रूप में छोड़ दिया है।

foldr (*) 1 [0..] -> 0*(foldr (*) 1 [1..]) 

तो क्योंकि अपने कस्टम गुणा ऑपरेटर myProduct दूसरा तर्क में सख्त यदि पहला तर्क है नहीं है शून्य, foldr myProduct 1 [0..] समाप्त कर सकते हैं: यह केवल एक कदम चलता है।

एक साइड नोट के रूप में, प्रीलूड उत्पाद फ़ंक्शन सीमित सूचियों तक सीमित है (और फ़ोल्डल के साथ कार्यान्वित किया जा सकता है)। यहां तक ​​कि अगर यह फ़ोल्डर का उपयोग करता है, तो शायद यह शॉर्टकट नहीं होगा क्योंकि मानक गुणा ऑपरेटर सख्त है; अन्यथा ऐसा करना सामान्य मामले में कम्प्यूटेशनल रूप से महंगा होगा जहां उत्पाद न तो शून्य हैं और न ही बंधे हैं।

-- sum and product compute the sum or product of a finite list of numbers. 

sum, product  :: (Num a) => [a] -> a 
sum    = foldl (+) 0 
product   = foldl (*) 1 

इसके अलावा, एक कारण यह फ़ोल्डर का उपयोग नहीं करता है; जैसा कि हम विस्तार और स्कैनल फ़ंक्शन में देख सकते थे, बाएं गुना गणना कर सकते हैं क्योंकि वे सूची का उपभोग करते हैं। सही फोल्ड, यदि ऑपरेटर शॉर्टकट नहीं करता है, तो सूची को स्वयं भी गणना के रूप में बड़े रूप में अभिव्यक्ति बनाने की आवश्यकता होती है। यह अंतर इसलिए है क्योंकि यह सबसे निचली अभिव्यक्ति है जो सख्त मामले में गणना शुरू करती है, लेकिन आंशिक अभिव्यक्ति जो परिणाम उत्पन्न करती है, आलसी मामले की अनुमति देती है। Haskell विकी में Lazy vs. non-strict मैं जितना संभव कर सकता हूं उससे बेहतर समझा सकता हूं, और यहां तक ​​कि उस पैटर्न मिलान का उल्लेख भी करता है, जिसे आपने मेरे उत्पाद में शॉर्टकट का वर्णन करने के लिए उपयोग किया था, सख्त हो सकता है।

Answer 2

आप पहली दो पंक्तियों स्विच करते हैं:

myProduct _ 0 = 0 
myProduct 0 _ = 0 
myProduct a b = a*b 

दूसरा तर्क हमेशा पहले एक से पहले मूल्यांकन किया जाएगा और अनंत foldr अब काम नहीं करेगा।

के बाद से अपने एक myProduct कि दोनों बहस शायद हम * होने के साथ बेहतर कर रहे हैं हमेशा का मूल्यांकन (यदि पहले 0 पहला है और मूल्यांकन नहीं दूसरा है अगर 0 दूसरे का मूल्यांकन नहीं) के लिए काम करता है lazily को परिभाषित करने के लिए असंभव दोनों अपनी तर्क।

Answer 3

आप इसे thusly हो सकता है:

myproduct xs = foldr op id xs 1 
    where 
    op x r acc = if x==0 then 0 else acc `seq` r (acc*x) 

यह एक सही गुना कि बाएं से संख्या गुणा करता है, लगातार अंतरिक्ष में सक्रिय है, और जैसे ही एक 0 का सामना करना पड़ा है बंद हो जाता है।