हैकेल में फ़ोल्डल की तुलना में धीमी गति क्यों है?

Question

ghc में डिफ़ॉल्ट sum कैसे foldl' (stricter equivalentfoldl) से 10 गुना धीमा है? समकक्ष? और यदि ऐसा है, तो इसे foldl' का उपयोग क्यों नहीं किया जाता है?

import Data.List 
> foldl' (+) 0 [1..10^7] 
50000005000000 
(0.39 secs, 963,528,816 bytes) 

> sum [1..10^7] 
50000005000000 
(4.13 secs, 1,695,569,176 bytes) 

पूर्णता के लिए यहां भी foldl और foldr के आँकड़े नहीं हैं।

> foldl (+) 0 [1..10^7] 
50000005000000 
(4.02 secs, 1,695,828,752 bytes) 

> foldr (+) 0 [1..10^7] 
50000005000000 
(3.78 secs, 1,698,386,648 bytes) 

लगता sum तरह foldl का उपयोग कर के बाद से उनकी क्रम इसी तरह की है कार्यान्वित किया जाता है। Ghc 7.10.2 पर परीक्षण किया।

Answer 1

sum समारोह GHC में foldl का उपयोग कर कार्यान्वित किया जाता है:

-- | The 'sum' function computes the sum of a finite list of numbers. 
sum      :: (Num a) => [a] -> a 
{-# INLINE sum #-} 
sum      = foldl (+) 0 

रूप in the source देखा जा सकता है।

यह इस तरह से होना चाहिए, क्योंकि यह विनिर्देश in the Haskell report है।

तर्क यह था कि सूची के कुछ आलसी तत्व प्रकारों के लिए foldl सही काम है। (मैं व्यक्तिगत रूप से लगता है foldl लगभग हमेशा गलत है और केवल foldl' इस्तेमाल किया जाना चाहिए कि।)

पर्याप्त अनुकूलन के साथ

, GHC कि परिभाषा इनलाइन जाएगा, यह हाथ में तत्व प्रकार के विशेषज्ञ, ध्यान दें कि पाश सख्त है, और बल प्रत्येक पुनरावृत्ति में संचयक का मूल्यांकन; इसे प्रभावी रूप से foldl' में बदलना, जैसा कि @ AndrásKovács द्वारा देखा गया है।

चूंकि जीएचसी-7.10, sum itselfFoldable प्रकार वर्ग का एक तरीका है, और डिफ़ॉल्ट परिभाषा foldMap के माध्यम से जाती है। instance Foldable [] हालांकि sum की उपरोक्त परिभाषा के साथ इसे ओवरराइड करता है।

Answer 2

@ जोआचिम ब्रेटनर के उत्तर को पूरक करने के लिए, मुझे यह blog post मिला, जो एक बहुत ही रोचक पढ़ा गया (लाल रंग की चर्चा से लिया गया, लिंक के लिए @ZhekaKozlov के लिए धन्यवाद)।

जब 24 साल पहले हास्केल 1.0 प्रकाशित हुआ था, तो कोई सीक फ़ंक्शन बिल्कुल नहीं था, इसलिए "क्लासिक" तरीके में फोल्ड को परिभाषित करने के अलावा कोई विकल्प नहीं था।

आखिरकार, छह साल बाद अधिक चर्चा के बाद, हमें हास्केल 1.3 में सीईसी फ़ंक्शन मिला। यद्यपि वास्तव में हास्केल 1.3 सीक में एक इवल वर्ग का हिस्सा था, इसलिए आप इसे कहीं भी इस्तेमाल नहीं कर पाएंगे, जैसे कि फोल्ड में। हास्केल 1.3 में आप प्रकार के साथ 'foldl परिभाषित करने के लिए प्राप्त हुआ होता है:

foldl' :: Eval b => (b -> a -> b) -> b -> [a] -> b 

हास्केल 1.4 और हास्केल 98 seq के लिए Eval वर्ग बाधा से छुटकारा मिला लेकिन foldl नहीं बदला गया। गले और जीएचसी और अन्य कार्यान्वयन ने गैर-मानक फोल्ड जोड़ा।

मुझे संदेह है कि लोगों ने इसे एक संगतता और जड़ता मुद्दा माना। एक गैर-मानक फोल्ड जोड़ने के लिए काफी आसान था 'लेकिन आप मानक को आसानी से बदल नहीं सकते हैं।

मुझे संदेह है कि अगर हमारे पास शुरुआत से सीक था तो हम इसका उपयोग करके फोल्ड को परिभाषित करते थे।

हास्केल की पूर्ववर्ती भाषाओं में से एक मिरांडा, पहले से ही हास्केल 1.0 से 5 साल पहले सीक था।

Btw, मैं

foldl1' (+) [1..10^7] 

तो का उपयोग करके 20 एमएस अधिक दाढ़ी बनाने के लिए प्रबंधित किया है, मुझे लगता है foldl1'sum और product के लिए डिफ़ॉल्ट (खाली सूचियों का विशेष हैंडलिंग के साथ) होना चाहिए।