सीखना हास्केल: गंभीर रूप से परिपत्र कार्यक्रम - कृपया

Question

की व्याख्या करने में सहायता करें मैं वर्तमान में डोट्स और वैन ईजक द्वारा "द हास्केल रोड टू लॉजिक, मैथ, और प्रोग्रामिंग" पुस्तक के माध्यम से जा रहा हूं। इस पुस्तक तक मुझे कभी भी किसी भी कार्यात्मक प्रोग्रामिंग भाषा के संपर्क में नहीं आया है, इसलिए इसे ध्यान में रखें।

फिर भी पुस्तक के शुरू में, यह एक primality परीक्षण के लिए निम्न कोड देता है:

ldp :: Integer -> Integer 
ldp n = ldpf primes1 n 

ldpf :: [Integer] -> Integer -> Integer 
ldpf (p:ps) n | rem n p == 0 = p 
       | p^2 > n  = n 
       | otherwise = ldpf ps n 

primes1 :: [Integer] 
primes1 = 2 : filter prime [3..] 

prime :: Integer -> Bool 
prime n | n < 1  = error "not a positive integer" 
     | n == 1 = False 
     | otherwise = ldp n == n 

जो प्रधानमंत्री कहता है, जो एलडीपी फिर से कहता है एक उचित रूप में परिपत्र प्रोग्रामिंग कि एलडीपी में चल रही primes1 कहता है, नहीं है। हालांकि पुस्तक यह निष्पादन के रूप में पेश करती है कि कार्यक्रम क्यों निष्पादित करता है और समाप्त करता है:

एलडीपी प्राइम नंबरों की सूची primes1 पर कॉल करता है। यह 'आलसी सूची' का पहला चित्रण है। सूची को 'आलसी' कहा जाता है क्योंकि हम केवल उस सूची का हिस्सा बनाते हैं जिसे हमें आगे की प्रक्रिया के लिए जरूरी है। प्राइम 1 को परिभाषित करने के लिए हमें प्रारंभिकता के लिए एक परीक्षण की आवश्यकता है, लेकिन यह परीक्षण स्वयं एलडी के संदर्भ में परिभाषित किया गया है, जो बदले में primes1 को संदर्भित करता है। हम एक सर्कल में चारों ओर दौड़ते प्रतीत होते हैं। इस सर्कल को 2 के लिए प्रारंभिक परीक्षण से परहेज करके गैर-दुष्परिणाम बनाया जा सकता है। यदि यह दिया जाता है कि 2 प्रमुख है, तो हम एलडी जांच में 2 की प्राथमिकता का उपयोग कर सकते हैं कि 3 प्रमुख है, और इसी तरह, और हम ऊपर हैं और

चल रहा जबकि मुझे लगता है कि मैं इस स्पष्टीकरण को समझते हैं, मैं बहुत यह जानना चाहेंगे अगर किसी laymen संदर्भ में समझा सकता है:

1. क्या एक "आलसी सूची" है और यह कैसे इस में लागू होता है संदर्भ?
2. यह जानकर कि 2 प्रमुख प्राइम प्रोग्राम को गैर-दुष्प्रभाव की अनुमति देता है?

किसी भी उत्तर की बहुत सराहना की जाती है।

Answer 1

आदेश में:

आलस्य केवल का मूल्यांकन भाव की संपत्ति के रूप में आप बल्कि जब आप संभवतः सकता है की तुलना में, की जरूरत है। एक आलसी सूची वह है जो संभवतः अनंत हो सकती है। स्पष्ट रूप से एक अनंत सूची का मूल्यांकन करने का प्रयास करना एक बुरा विचार होगा यदि मूल्यांकन आलसी नहीं था।

मुझे यकीन है कि क्या "गैर शातिर" का अर्थ है नहीं कर रहा हूँ, लेकिन मैं आपको मिल जाएगा कि एक ज्ञात प्रधानमंत्री के रूप में मान "2" होने प्रत्यावर्तन के लिए एक आधार मामले प्रदान करता है लगता है, यानी यह एक विशेष प्रदान करता है इनपुट जिस पर कार्यक्रम समाप्त हो जाएगा। एक पुनरावर्ती कार्य (या वास्तव में पारस्परिक रूप से पुनरावर्ती कार्यों का एक सेट) लिखना आम तौर पर आवेदन के लगातार चरणों में इस आधार मामले की ओर कुछ इनपुट मूल्य को कम करना शामिल है।

संदर्भ के लिए, इस आकार के प्रोग्राम टुकड़े आमतौर पर पारस्परिक रूप से रिकर्सिव कहा जाता है। "परिपत्र संदर्भ" शब्द वह नहीं है जिसे आप वास्तव में इस मामले में लागू करेंगे।

Answer 2

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

1. गणना का मूल्य आवश्यक कुछ और है कि करने के लिए आवश्यक गणना करने के लिए है ...
2. आपने हास्केल को अन्य चीज़ों की तुलना में जल्द से जल्द गणना करने के लिए कहा था।

तो primes1 समारोह Integer मानों की सूची पैदा करता है, लेकिन यह किसी भी अधिक का उत्पादन नहीं करता आवश्यकता से अधिक समग्र गणना को पूरा करने के। फिर भी, यदि आप इसे इस तरह से परिभाषित:

primes1 :: [Integer] 
primes1 = filter prime [2..] 

आप एक समस्या होगी। primes1prime 2 का मूल्यांकन करने वाले (अप्रत्यक्ष रूप से) के अनुक्रम में पहला मान उत्पन्न करने का प्रयास करेगा, जो ldp 2 का मूल्यांकन करेगा, जो primes1 द्वारा उत्पादित पहले मान के लिए पूछेगा ... presto अनंत लूप!

primes1 द्वारा उत्पन्न अनुक्रम के पहले मान के रूप में सीधे 2 लौटकर, आप अनंत लूप से बचें। अनुक्रम में उत्पन्न प्रत्येक बाद के मान के लिए, primes1 पहले से ही पिछले मान उत्पन्न कर चुका है जिसका मूल्यांकन बाद के मूल्य की गणना के हिस्से के रूप में ldp द्वारा किया जाएगा।

Answer 3

ध्यान देने वाली पहली बात यह है कि अपने कोड पर कुछ भी नहीं करता है। यह केवल गणितीय अभिव्यक्तियों का एक गुच्छा है और इससे कोई फर्क नहीं पड़ता कि यह तब तक कितना परिपत्र है जब तक हम उनसे कुछ मूल्य निकालने का प्रयास नहीं करते हैं। हम यह कैसे करे?

हम कर सकता है:

print $ take 1 primes1 

यहां कोई समस्या नहीं है।

print $ take 3 primes1 

के primes1 का विस्तार कुछ मान बाहर निकलने के लिए कोशिश करते हैं: हम पुनरावर्ती कोड के किसी भी को देखे बिना primes1 के प्रथम मान ले जा सकते हैं, यह वहाँ 2. के बारे में के रूप में स्पष्ट रूप से है। इन अभिव्यक्तियों को प्रबंधित करने के लिए, अब मैं print और take भागों को अनदेखा कर रहा हूं, लेकिन याद रखें कि हम केवल इसलिए ही इस काम को कर रहे हैं। primes1 है:

primes1 = 2 : filter prime [3..] 

हमने अपने पहले मूल्य है, और हमारे दूसरे पहला कदम फिल्टर विस्तार हो रहा है। यदि यह एक सख्त भाषा थी तो हम पहले [3 ..] का विस्तार करने की कोशिश करेंगे और अटक जाएंगे। फिल्टर का एक संभावित परिभाषा है:

filter f (x:xs) = if f x then x : filter f xs else filter f xs 

जो देता है:

primes1 = 2 : if prime 3 then 3 : filter prime [4..] else filter prime [4..] 

हमारा अगला कदम पता लगाना जा सकता है अगर prime 3 सही या गलत है, तो चलो prime के बारे में हमारी परिभाषाओं का उपयोग कर इसे विस्तार करते हैं, ldp और ldpf।

primes1 = 2 : if ldp 3 == 3 then 3 : filter prime [4..] else filter prime [4..] 
primes1 = 2 : if ldpf primes1 3 == 3 then 3 : filter prime [4..] else filter prime [4..] 

अब, बातें दिलचस्प, primes1 संदर्भ में ही मिलता है और ldpf इसकी गणना करने के लिए पहले मूल्य की जरूरत है। सौभाग्य से, हम आसानी से पहला मूल्य प्राप्त कर सकते हैं।

primes1 = 2 : if ldpf (2 : tail primes) 3 == 3 then 3 : filter prime [4..] else filter prime [4..] 

अब, हम गार्ड खंड ldpf में इसलिए ldpf (2 : tail primes) 3 = 3 लागू करते हैं और 2^2 > 3 मिल जाए,।

primes1 = 2 : if 3 == 3 then 3 : filter prime [4..] else filter prime [4..] 
primes1 = 2 : 3 : filter prime [4..] 

अब हमारे पास दूसरा मूल्य है। ध्यान दें कि हमारे मूल्यांकन का दायां हाथ कभी विशेष रूप से बड़ा नहीं होता और हमें कभी भी रिकर्सिव लूप का पालन करने की आवश्यकता नहीं है।

primes1 = 2 : 3 : if prime 4 then 4 : filter prime [5..] else filter prime [5..] 
primes1 = 2 : 3 : if ldp 4 == 4 then 4 : filter prime [5..] else filter prime [5..] 
primes1 = 2 : 3 : if ldpf primes1 4 == 4 then 4 : filter prime [5..] else filter prime [5..] 
primes1 = 2 : 3 : if ldpf (2 : tail primes1) 4 == 4 then 4 : filter prime [5..] else filter prime [5..] 

हम गार्ड खंड rem 4 2 == 0 उपयोग करते हैं, इसलिए हम 2 यहाँ मिलता है।

primes1 = 2 : 3 : if 2 == 4 then 4 : filter prime [5..] else filter prime [5..] 
primes1 = 2 : 3 : filter prime [5..] 
primes1 = 2 : 3 : if prime 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : if ldp 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : if ldpf primes1 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : if ldpf (2 : tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 

कोई गार्ड मैचों, तो हम recurse:

primes1 = 2 : 3 : if ldpf (tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : if ldpf (3 : tail (tail primes)) 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 

अब 3^2 > 5 ताकि अभिव्यक्ति 5.

primes1 = 2 : 3 : if 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : 5 : filter prime [6..] 

हम केवल तीन मूल्यों की आवश्यकता है, इसलिए मूल्यांकन रोक सकता है।

तो, अब अपने सवालों के जवाब देने के लिए। एक आलसी सूची वह है जो हमें केवल हमें आवश्यकतानुसार मूल्यांकन करने की आवश्यकता होती है, और 2 मदद करता है क्योंकि यह सुनिश्चित करता है कि जब हम रिकर्सिव चरण तक पहुंचते हैं तो हमारे पास हमेशा पहले से ही की गणना की जाती है। (कल्पना करें कि उस अभिव्यक्ति को विस्तारित करने के लिए अगर हम 2 को नहीं जानते थे, तो हम एक लूप सुंदर में फंस गए थे।)