हस्केल: अनंत सूची जब पूर्णांक को स्टैक कार्यान्वयन के लिए धकेल दिया जाता है

Aug 17 2020

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

अन्य सभी कार्य वैसे ही होते हैं जैसे मैं उनसे उम्मीद करता हूं लेकिन मैं इस समस्या को नहीं समझता push। यह गलत हो जाता है जब मैं अपने आप को एक खाली स्टैक सौंपने की कोशिश करता हूं जिसने निम्नलिखित की तरह एक चर को धक्का दिया है:

λ > a = makeStack
λ > push 3 a
[3]
λ > a
[]
λ > a = push 3 a
λ > a
[3,3,3,3,3,3,3,3,3,3^CInterrupted.
type Stack a = [a]

makeStack :: Stack a 
makeStack = []

push :: a -> Stack a -> Stack a
push a as = (a:as)

जवाब

8 RobinZigmond Aug 17 2020 at 16:52

हास्केल उत्परिवर्तन की अनुमति नहीं देता है। एक स्रोत फ़ाइल में, यदि आप एक चर को परिभाषित करते हैं aऔर फिर इसे पुन: असाइन करने का प्रयास करते हैं, जैसा कि आप यहां करते हैं a = push 3 a, तो आपको एक जटिल त्रुटि मिलेगी। एकमात्र कारण यह नहीं है कि आप जीएचसीआई में काम कर रहे हैं, जो आपको चर को फिर से परिभाषित करने की अनुमति देता है - यह विशुद्ध रूप से एक सुविधा है इसलिए आपको विभिन्न परिभाषाओं के साथ प्रयोग करते हुए नए नामों पर विचार करने की आवश्यकता नहीं है।

और, महत्वपूर्ण बात, a = push 3 aहै एक नया मान दे रही है aपिछले एक पर आधारित है, के रूप में यह एक अनिवार्य भाषा में किया जाएगा। इसके बजाय, यह a स्वयं के संदर्भ में एक परिभाषा है

इसलिए आपको एक अनंत सूची मिलती है - आपकी परिभाषा इस प्रकार है:

a = push 3 a
   = 3:a
   = 3:(push 3 a)
   = 3:(3:a)

और इसी तरह। हास्केल के आलस्य के कारण, इस तरह की परिभाषा के साथ कोई समस्या नहीं है - जीएचसीआई, जब आप पूरी सूची के लिए पूछेंगे, तो यहां, बस एक बार में एक तत्व की गणना करें, और इसलिए जब तक आप इसे रोकने के लिए नहीं कहते हैं, तब तक 3s छपाई करते रहें।

आप जो चाहते हैं उसे पाने के लिए, आपको या तो बस टाइप करने की ज़रूरत है push 3 a, या यदि आपको इसे एक नाम निर्दिष्ट करने की आवश्यकता है, तो बस एक अलग नाम चुनें ab = push 3 aइसके बाद bजैसा आप उम्मीद करेंगे वैसा ही व्यवहार करेंगे।

4 ZhiltsoffIgor Aug 17 2020 at 16:49

हैसेल में चर (मेरी अनुमान, लगभग) कोई भी परिवर्तनशील नहीं है (मेरी शब्दावली को सुधारने के लिए @amalloy के लिए धन्यवाद)।

यदि आप ऐसा कुछ लिखते हैं:

x = f x

यह एक अनंत लूप में प्रवेश करता है: f (f (f ...

इसलिए, इसका कोई पिछला मूल्य नहीं aहै जिसमें 3धक्का दिया जा सकता है।

इसलिए, आपको push 3 aकुछ अन्य मूल्य (या उस मामले के लिए सीधे ghci में) डालना होगा ।

हालांकि ऐसा लूप कभी-कभी काम आ सकता है। पर एक नज़र रखना Data.Function.fix:

fix :: (a -> a) -> a
fix f = let x = f x in x

इसका उपयोग वही किया जा सकता है जो आप करते हैं:

GHCi> fix (push 3)
[3,3,3,3,^CInterrupted.

फिर भी, अनंत लूप हमेशा ऐसा नहीं होता है। जरा देखो तो:

factFun rec n = if n == 0 then 1 else n * rec (n - 1)

यह फ़ंक्शन फैक्टरियल की तरह लग सकता है, फिर भी गैर-समाप्ति शाखा में पुनरावर्ती कॉल को डमी ( rec) के साथ बदल दिया जाता है । हम चाहते हैं कि इस डमी factFunको फिर से जगह मिले और बार-बार फैक्ट्री प्राप्त हो। fixक्या ये:

GHCi> fix factFun 4
24

नोट: मैं अपनी टिप्पणी यहां दूंगा: यदि पाठक को fixअभी तक पता नहीं है, तो मैं उन्हें एक लंबी और दिलचस्प यात्रा पर आमंत्रित करना चाहता हूं। मेरा सुझाव है कि वे इस विकिकट के साथ डेनेटेशनल शब्दार्थ पर शुरू करते हैं ।