जीएचसी हास्केल में स्वचालित रूप से ज्ञापन कब होता है?

Question

मैं समझ नहीं क्यों एम 1 जाहिरा तौर पर memoized है, जबकि एम 2 में नहीं है निम्नलिखित:

m1  = ((filter odd [1..]) !!) 

m2 n = ((filter odd [1..]) !! n) 

एम 1 10000000 पहली कॉल पर लगभग 1.5 सेकंड लेता है, और कहा कि आगामी कॉल पर का एक अंश (संभवतः यह सूची कैश), जबकि एम 2 10000000 हमेशा एक ही समय लेता है (प्रत्येक कॉल के साथ सूची का पुनर्निर्माण)। कोई विचार क्या चल रहा है? क्या अंगूठे के कोई नियम हैं कि क्या और जब जीएचसी एक समारोह को याद रखेगा? धन्यवाद।

Answer 1

जीएचसी कार्यों को याद नहीं करता है।

हालांकि, यह कोड में किसी दिए गए अभिव्यक्ति को प्रति बार एक बार गणना करता है कि इसके आसपास के लैम्ब्डा-अभिव्यक्ति दर्ज की जाती है, या सबसे अधिक बार यह शीर्ष स्तर पर होती है। निर्धारण जहां लैम्ब्डा-अभिव्यक्ति कर रहे हैं एक छोटे से मुश्किल है जब आप अपने उदाहरण की तरह वाक्यात्मक चीनी का उपयोग किया जा सकता है, तो चलो बराबर desugared वाक्य रचना करने के लिए इन कन्वर्ट करते हैं:

m1' = (!!) (filter odd [1..])    -- NB: See below! 
m2' = \n -> (!!) (filter odd [1..]) n 

(नोट: हास्केल 98 रिपोर्ट वास्तव में एक छोड़ दिया ऑपरेटर का वर्णन करता है (a %) तरह अनुभाग \b -> (%) a b के रूप में बराबर है, लेकिन GHC (%) a करने के लिए इसे desugars। ये तकनीकी रूप से अलग हैं, क्योंकि वे द्वारा seq। मुझे लगता है कि मैं इस बारे में GHC Trac टिकट प्रस्तुत हो सकता है प्रतिष्ठित किया जा सकता।)

इस को देखते हुए, आप कर सकते हैं देखें कि m1' में, अभिव्यक्ति filter odd [1..] निहित नहीं है I n किसी भी lambda- अभिव्यक्ति, तो यह केवल आपके प्रोग्राम के प्रति रन के बाद गणना की जाएगी, जबकि m2', filter odd [1..] प्रत्येक बार लैम्ब्डा-अभिव्यक्ति दर्ज की जाएगी, यानी m2' के प्रत्येक कॉल पर गणना की जाएगी। इससे आप जो समय देख रहे हैं उसमें अंतर बताते हैं।

---

दरअसल, कुछ ऑप्टिमाइज़ेशन विकल्पों के साथ जीएचसी के कुछ संस्करण उपरोक्त वर्णन से अधिक मूल्य साझा करेंगे। यह कुछ स्थितियों में समस्याग्रस्त हो सकता है। उदाहरण के लिए, समारोह

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x]) 

पर विचार

GHC देख सकते हैं कि y

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x]) 

इस मामले में करने के लिए x पर निर्भर करते हैं और फिर से लिखने नहीं करता समारोह, नए संस्करण में काफी कम कुशल है, क्योंकि यह होगा स्मृति से लगभग 1 जीबी पढ़ने के लिए जहां y संग्रहीत किया जाता है, जबकि मूल संस्करण निरंतर स्थान पर चलाया जाता है और प्रोसेसर के कैश में फिट होता है। वास्तव में, GHC 6.12.1 के तहत, समारोह f लगभग दो बार के रूप में तेजी से जब बिना अनुकूलन संकलित की तुलना में यह -O2 साथ संकलित किया गया है है।

Answer 2

एम 1 केवल एक बार गणना की है क्योंकि यह एक लगातार अनुप्रयोगी फार्म है, जबकि एम 2 एक सीएएफ नहीं है, और इसलिए प्रत्येक मूल्यांकन के लिए की जाती है है। monomorphism प्रतिबंध एम 1 पर लागू होता है, लेकिन एम 2 नहीं, क्योंकि एम 2 स्पष्ट रूप से तर्क दिया गया है: http://www.haskell.org/haskellwiki/Constant_applicative_form

Answer 3

वहाँ दो रूपों के बीच एक महत्वपूर्ण अंतर है:

cafs पर GHC विकि देखें। तो एम 2 का प्रकार सामान्य है लेकिन एम 1 विशिष्ट है।प्रकार वे आवंटित कर रहे हैं कर रहे हैं:

m1 :: Int -> Integer 
m2 :: (Integral a) => Int -> a 

अधिकांश हास्केल compilers और दुभाषियों (उन सभी को है कि मैं वास्तव में पता) बहुरूपी संरचनाओं memoize नहीं है, इसलिए एम 2 के आंतरिक सूची हर बार निर्मित है यह, कहा जाता है जहां एम 1 के नहीं है ।

Answer 4

मुझे यकीन नहीं है, क्योंकि मैं खुद हास्केल के लिए काफी नया हूं, लेकिन ऐसा प्रतीत होता है कि यह दूसरा फ़ंक्शन पैरामीटर है और पहला वाला नहीं है। फ़ंक्शन की प्रकृति यह है कि, इसका परिणाम इनपुट मान पर निर्भर करता है और कार्यात्मक प्रतिमान में especailly यह केवल इनपुट पर निर्भर करता है। स्पष्ट निहितार्थ यह है कि कोई पैरामीटर वाला फ़ंक्शन हमेशा वही मान देता है, इससे कोई फर्क नहीं पड़ता।

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

primes = filter isPrime [2..] 
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n] 
     where f `divides` n = (n `mod` f) == 0 

तो यह परीक्षण करने के लिए, मैं GHCi में प्रवेश किया और लिखा है: primes !! 1000। इसमें कुछ सेकंड लग गए, लेकिन आखिरकार मुझे जवाब मिला: 7927। तब मैंने primes !! 1001 कहा और तुरंत जवाब मिला। इसी तरह एक पल में मुझे take 1000 primes का नतीजा मिला, क्योंकि हास्केल को पूरी हज़ार-तत्व सूची की गणना करने के लिए पहले 1001 तत्वों को वापस करना था।

इस प्रकार यदि आप अपना कार्य लिख सकते हैं जैसे कि इसमें कोई पैरामीटर नहीं है, तो आप शायद इसे चाहते हैं। ;)