क्या हास्केल में चक्रीय सूचियों का पता लगाने की क्षमता भाषा के किसी भी गुण को तोड़ देगी?

Question

हास्केल में, कुछ सूचियों चक्रीय हैं:

ones = 1 : ones 

दूसरों नहीं हैं:

nums = [1..] 

और फिर वहाँ इस तरह की बातें कर रहे हैं:

more_ones = f 1 where f x = x : f x 

यह ones रूप में एक ही मूल्य को दर्शाता है , और निश्चित रूप से वह मान एक दोहराव अनुक्रम है। लेकिन क्या यह चक्रीय डेटा संरचना के रूप में स्मृति में दर्शाया गया है संदिग्ध है। (एक कार्यान्वयन ऐसा करने के सकता है, लेकिन this answer explains that "it's unlikely that this will happen in practice"।)

मान लीजिए हम एक हास्केल कार्यान्वयन लेते हैं और इसे हैक निर्मित एक समारोह isCycle :: [a] -> Bool कि तर्क के में स्मृति प्रतिनिधित्व की संरचना जांच करता है। यह True देता है यदि सूची शारीरिक रूप से चक्रीय है और False है तो तर्क सीमित लंबाई का है। अन्यथा, यह समाप्त करने में विफल हो जाएगा। (मैं "में यह हैकिंग" कल्पना क्योंकि यह हास्केल में है कि समारोह में लिखने के लिए असंभव है।)

इस समारोह के अस्तित्व भाषा के किसी भी दिलचस्प गुण तोड़ सकते हैं?

Answer 1

क्या इस समारोह का अस्तित्व भाषा के किसी भी दिलचस्प गुण को तोड़ देगा?

हाँ यह होगा। यह referential transparency तोड़ देगा (the Wikipedia article भी देखें)। एक हास्केल अभिव्यक्ति हमेशा इसके मूल्य से प्रतिस्थापित किया जा सकता है। दूसरे शब्दों में, यह केवल पारित तर्कों पर निर्भर करता है और कुछ भी नहीं। अगर हमारे पास

isCycle :: [a] -> Bool 

जैसा कि आप प्रस्तावित करते हैं, इसका उपयोग करके अभिव्यक्ति इस संपत्ति को और संतुष्ट नहीं करेंगे। वे मूल्यों की आंतरिक स्मृति प्रतिनिधित्व पर निर्भर कर सकते हैं। नतीजतन, अन्य कानूनों का उल्लंघन किया जाएगा। उदाहरण के लिए identity lawFunctor के लिए

fmap id === id 

किसी भी अधिक पकड़ नहीं होगा: बाद के रूप में अचक्रीय होगा आप ones और fmap id ones के बीच भेद करने में सक्षम होगी। और उपरोक्त कानून को लागू करने जैसे संकलक अनुकूलन अब प्रोग्राम गुणों को संरक्षित नहीं करेंगे।

हालांकि एक और सवाल होने समारोह

isCycleIO :: [a] -> IO Bool 

रूप IO कार्यों की जांच करने और कुछ भी बदलने की अनुमति दी जाती है किया जाएगा।

import qualified Data.Foldable as F 

data SmartList a = Cyclic [a] | Acyclic [a] 

instance Functor SmartList where 
    fmap f (Cyclic xs) = Cyclic (map f xs) 
    fmap f (Acyclic xs) = Acyclic (map f xs) 

instance F.Foldable SmartList where 
    foldr f z (Acyclic xs) = F.foldr f z xs 
    foldr f _ (Cyclic xs) = let r = F.foldr f r xs in r 

बेशक

यह अगर एक सामान्य सूची चक्रीय है या नहीं, पहचान करने में सक्षम नहीं होगा, लेकिन के लिए कई आपरेशनों:

एक शुद्ध समाधान एक डेटा प्रकार है कि आंतरिक रूप से दो अलग करने के लिए हो सकता है Cyclic मान रखने के ज्ञान को संरक्षित करना संभव होगा।

Answer 2

सामान्य मामले में, नहीं, आप चक्रीय सूची की पहचान नहीं कर सकते हैं। हालांकि अगर सूची एक खुला ऑपरेशन द्वारा उत्पन्न की जा रही है तो आप कर सकते हैं। Data.List इस में शामिल हैं:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

पहला तर्क एक समारोह है कि एक "राज्य" प्रकार के तर्क "बी" लेता है और सूची का एक तत्व और एक नए राज्य वापस आ सकते हैं है। दूसरा तर्क प्रारंभिक राज्य है। "कुछ भी नहीं" का मतलब है कि सूची समाप्त होती है।

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