क्यों फ़ोल्डल और एफएन फ़ंक्शन के साथ छोटा सर्किटिंग नहीं है?

Question

मेरे समझ के साथ कि foldl और foldr तरह निष्पादित होता है:

foldl f a [1..30] =>(f (f (f ... (f a 1) 2) 3) ... 30)

और

foldr f a [1..30] =>(f 1 (f 2 (f 3 (f ....(f 30 a)))))..)

तो .. foldr (&&) False (repeat False)(&&) False ((&&) False (....)) पहले देखता है के रूप में सबसे बाहरी f देखता shortciruit कर सकते हैं तर्क के रूप में तर्क और दूसरे तर्क का मूल्यांकन करने की आवश्यकता नहीं है (जो एक बड़ा थंक है)।

तो

andFn :: Bool -> Bool -> Bool 
andFn _ False = False 
andFn x True = x 

और

foldl andFn True (repeat False) -- => 

-- (andFn (andFn ...(andFn True False) ... False) False) 
-- ^^ outermost andFn 

साथ क्या होता है लेकिन इस हमेशा के लिए ले जा रहा है।

मैंने सोचा था कि outermost andFn पता होगा कि कि दूसरा तर्क पर मिलान पैटर्न से, जवाब False है ..

यहाँ और क्या हो रहा है?

Answer 1

andFn पर तर्कों के क्रम से foldr और foldl के बीच एक बड़ा अंतर है।

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

सूचना कैसे foldr तुरंत f करने के लिए नियंत्रण हस्तांतरित कर देता है: यदि f आलसी है यह foldr f z xs की गणना से बच सकते हैं।

इसके बजाय, foldl स्थानान्तरण नियंत्रित करने के लिए ... foldl: समारोह f केवल शुरू जब आधार मामले

foldl f z [] = z  -- z contains the chained f's, which NOW get evaluated 

तक पहुँच जाता है इस्तेमाल किया जा रहा इसलिए foldl f z infiniteList होगा हमेशा हट जाना, कोई बात नहीं क्या f है: किसी वास्तविक गणना के होने से पहले पूरे infiniteList को पूरी तरह से पुन: सक्रिय करने की आवश्यकता है। (विषय से बाहर: यही कारण है कि, तब भी जब यह काम करता है, foldl अक्सर भयानक प्रदर्शन है, और foldl' और अधिक अभ्यास में इस्तेमाल किया जाता है।)

विशेष रूप से, तैनात उदाहरण

foldl andFn True (repeat False) -- => 
-- (andFn (andFn ...(andFn True False) ... False) False) 
-- ^^ outermost andFn 

आंशिक रूप से गलत है। "बाहरीतम andFn" वास्तव में अंतिम एक होगा, यानी तत्व repeat False में से संबंधित एक से संबंधित होगा। लेकिन ऐसा कोई जानवर नहीं है।