हास्केल में, ऐसी चीजों के लिए टाइप क्लास क्यों नहीं है जो सूचियों की तरह कार्य कर सकें?

Question

मैं Learn You a Haskell पढ़ रहा हूँ और मैं सोच रहा हूँ क्यों इतनी सारी चीजें एक सूची की तरह कार्य कर रहे हैं, और प्रस्तावना में कुछ भी नहीं प्रकार की कक्षाओं में सुविधा का उपयोग कर रहा है इस सेट करने के लिए:

"bytestring संस्करण का: विपक्ष कहा जाता है यह एक बाइट और एक बाईटरिंग लेता है और बाइट को शुरुआत में रखता है। हालांकि यह आलसी है, इसलिए यह एक नया हिस्सा बना देगा, भले ही बाइटस्ट्रिंग में पहला हिस्सा भरा न हो। यही कारण है कि इसका उपयोग करना बेहतर है विपक्ष का सख्त संस्करण, विपक्ष 'यदि आप एक बाइटिंग की शुरुआत में बहुत से बाइट डालने जा रहे हैं। "

क्यों दिया गया TypeClass listable या कुछ को एकजुट करने के : समारोह प्रदान करता है कि नहीं है Data.ByteString, Data.List, Data.ByteString.Lazy, आदि? क्या इसका कोई कारण है, या यह विरासत हास्केल का सिर्फ एक तत्व है? एक उदाहरण के रूप : का उपयोग करते हुए एक ख़ामोश की तरह है, यह भी LYAH से:

अन्यथा, bytestring मॉड्यूल कार्यों कि सहित Data.List, में उन लोगों के अनुरूप हैं का भार है, लेकिन करने के लिए, सिर सीमित नहीं है, पूंछ, init, अशक्त, लंबाई, नक्शे, रिवर्स, foldl, foldr, concat, takeWhile, फिल्टर, आदि

Answer 1

प्रदान करता है कि: Data.ByteString, Data.List, Data.ByteString एकजुट करने के लिए समारोह आलसी, आदि?

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

एक ही इंटरफेस के साथ इन विभिन्न अर्ध-संबंधित डेटा प्रकारों को एकजुट करने के लिए कुछ परियोजनाएं हैं, इसलिए मुझे उम्मीद है कि हम जल्द ही परिणाम देखेंगे। इसी तरह कंटेनर प्रकार के लिए। परिणाम हालांकि मामूली नहीं होगा।

Answer 2

ListLike पैकेज जो आप ढूंढ रहे हैं उसे प्रदान करने के लिए प्रतीत होता है। मैंने कभी नहीं समझा है कि यह अधिक लोकप्रिय क्यों नहीं है।

सूची एक तरफ, एक कारण यह प्रीलूड में लागू नहीं किया गया है क्योंकि कुछ भाषा एक्सटेंशन (बहु-पैरा प्रकार के वर्ग और फंडप या संबंधित प्रकार) का आह्वान किए बिना ऐसा करना संभव नहीं है। वहाँ कंटेनरों के तीन प्रकार के विचार करने के लिए कर रहे हैं:

1. कंटेनर है कि सभी पर अपने तत्वों के बारे में परवाह नहीं है (उदाहरण के लिए [])
2. कंटेनर जो केवल (जैसे bytestrings)
3. कंटेनरों विशिष्ट तत्वों के लिए लागू किया जाता है जो तत्वों पर बहुलक हैं लेकिन संदर्भ (उदाहरण के लिए Data.Vector.Storable, जो किसी भी प्रकार को एकउदाहरण के साथ रखेगा) की आवश्यकता है।

यहाँ किसी भी एक्सटेंशन का उपयोग किए बिना एक बहुत ही बुनियादी ListLike शैली वर्ग है:

class Listable container where 
    head :: container a -> a 

instance Listable [] where 
    head (x:xs) = x 

instance Listable ByteString where --compiler error, wrong kind 

instance Listable SV.Vector where 
    head v = SV.head --compiler error, can't deduce context (Storable a) 

यहाँ container तरह *->* है। यह bytestrings के लिए काम नहीं करेगा क्योंकि वे एक मनमाना प्रकार की अनुमति नहीं है; उनके पास * है। यह डेटा के लिए भी काम नहीं करेगा। वेक्टर। स्टेटिकल वेक्टर, क्योंकि कक्षा में संदर्भ (स्टेरियल बाधा) शामिल नहीं है।

आप

class ListableMPTC container elem | container -> elem where 

या

class ListableAT container where 
    type Elem container :: * 

अब container या तो अपने वर्ग परिभाषा बदलकर इस समस्या को ठीक कर सकते हैं प्रकार * है; यह एक पूरी तरह से लागू प्रकार का कन्स्ट्रक्टर है। यही है, आपके उदाहरण

instance ListableMPTC [a] a where 

जैसा दिखते हैं लेकिन अब आप Haskell98 नहीं हैं।

यही कारण है कि एक साधारण सूची-प्रकार इंटरफ़ेस भी गैर-तुच्छ है; जब आपके पास अलग-अलग संग्रह semantics खाते हैं (उदा। कतार) के लिए यह थोड़ा कठिन हो जाता है। दूसरी वास्तव में बड़ी चुनौती उत्परिवर्तनीय बनाम-अपरिवर्तनीय डेटा है। अब तक मैंने जो भी प्रयास देखा है (एक को छोड़कर) उस मुद्दे पर एक परिवर्तनीय इंटरफ़ेस और एक अपरिवर्तनीय बनाकर पेंट करता है। एक इंटरफ़ेस जो मुझे पता है, दोनों ने एकजुट किया था, वह दिमागी झुकाव था, विस्तार का एक समूह लगा, और काफी खराब प्रदर्शन था।

परिशिष्ट: bytestrings

पूरी तरह से मेरी ओर से अनुमान है, लेकिन मैं हम विकास के एक उत्पाद के रूप bytestrings के साथ फंस रहे हैं लगता है। यही है, वे कम प्रदर्शन I/O संचालन का पहला समाधान थे, और आईओ सिस्टम कॉल के साथ इंटरफेसिंग के लिए Ptr Word8 एस का उपयोग करना समझ में आया। पॉइंटर्स पर संचालनों को स्टेरियल की आवश्यकता होती है, और सबसे अधिक संभावना है कि पॉलिमॉर्फिज्म काम करने के लिए आवश्यक एक्सटेंशन (ऊपर वर्णित अनुसार) उपलब्ध न हों। अब उनकी गति को दूर करना मुश्किल है। Polymorphism के साथ एक समान कंटेनर निश्चित रूप से संभव है, storablevector पैकेज यह लागू करता है, लेकिन यह कहीं भी लोकप्रिय के करीब नहीं है।

क्या बाइटस्टर्स तत्वों पर किसी भी प्रतिबंध के बिना पॉलिमॉर्फिक हो सकता है? मुझे लगता है कि निकटतम हास्केल को यह ऐरे प्रकार है। यह निम्न स्तर के आईओ के लिए एक बाईस्ट्रिंग के रूप में उतना ही अच्छा नहीं है क्योंकि पॉइंटर से डेटा को सरणी के आंतरिक प्रारूप में अनपॅक करने की आवश्यकता है। इसके अलावा डेटा बॉक्स किया गया है, जो महत्वपूर्ण जगह ओवरहेड जोड़ता है। यदि आप अनबॉक्स किए गए संग्रहण (कम स्थान) और सी के साथ कुशल इंटरफेसिंग चाहते हैं, तो पॉइंटर्स जाने का तरीका हैं। एक बार आपके पास पीआरटी हो जाने के बाद, आपको स्टेलेबल की आवश्यकता होती है, और फिर आपको टाइप क्लास में तत्व प्रकार शामिल करने की आवश्यकता होती है, इसलिए आपको एक्सटेंशन की आवश्यकता होती है।

कहा जा रहा है कि, मुझे लगता है कि उपलब्ध उचित एक्सटेंशन के साथ यह अनिवार्य रूप से किसी एकल कंटेनर कार्यान्वयन (मॉड्यूलो म्यूटेबल/अपरिवर्तनीय एपीआई) के लिए एक हल समस्या है। कठिन हिस्सा अब कक्षाओं के एक समझदार सेट के साथ आ रहा है जो कई अलग-अलग प्रकार की संरचनाओं (सूचियों, सरणी, कतार आदि) के लिए प्रयोग योग्य हैं और उपयोगी होने के लिए पर्याप्त लचीला है। मैं व्यक्तिगत रूप से अपेक्षाकृत सीधा होने की उम्मीद करता हूं, लेकिन मैं गलत हो सकता था।

Answer 3

बाइटस्ट्रिंग एक सामान्य प्रकार नहीं है।

अन्य भाषाओं में, सभी सूची-जैसे डेटा संरचनाओं के लिए Sequence जैसे कुछ है। मैं इस काम करता है, सही एक्सटेंशन के साथ लगता है:

class Seq a b | a -> b where 
    head :: a -> b 
    isTail :: a -> Bool 

# ([a]) is a sequence of a's 
instance Seq [a] a where 
    head (x:xs) = x 
    isTail = (== []) 

# ByteString is a sequence of chars 
instance Seq ByteString Char 

या इस कोशिश?

type BS a = ByteString 
instance List BS 

Answer 4

वहाँ मूल्य का एक बहुत हास्केल में सूची की तरह डेटा के लिए एक प्रकार वर्ग होने के लिए नहीं है। क्यूं कर? आलस्य के कारण । आप केवल एक फ़ंक्शन लिख सकते हैं जो आपके डेटा को एक सूची में परिवर्तित करता है, और उसके बाद उस सूची का उपयोग करता है। सूची केवल अपने उपन्यासकारों के रूप में बनाई जाएगी और तत्वों की मांग की जा रही है, और जैसे ही कोई संदर्भ उपसर्गों में नहीं रहता है, उनकी स्मृति संग्रह के लिए योग्य होगी।

एक प्रकार की श्रेणी के लिए मूल्य है जो सामान्य toList फ़ंक्शन प्रदान करता है-हालांकि, यह पहले से ही Data.Foldable में मौजूद है।

तो मूल रूप से, समाधान Data.Foldable को लागू करना है और इसके toList फ़ंक्शन का उपयोग करना है।

Answer 5

ऐसी कक्षा के साथ मुख्य समस्या यह है कि यहां तक ​​कि यदि यह अस्तित्व में है तो यह केवल एक सतही समानता प्रदान करेगा।

asymptotics विभिन्न संरचनाओं का उपयोग कर काफी भिन्नता होगी बनाया ही एल्गोरिथ्म के।

सख्त बाइटस्ट्रेशंस के मामले में उन्हें विपक्ष के साथ बनाने के मामले में भयानक है, क्योंकि जब भी आप एक और चार जोड़ते हैं तो आप पूरे स्ट्रिंग को कॉपी करते हैं। यह ओ (1) किसी सूची पर ऑपरेशन इसे ओ (एन) ऑपरेशन को बायटेस्ट्रिंग पर बदल देता है।

यह हे की ओर जाता है (एन^2) व्यवहार जब आप पहली बार एल्गोरिथ्म है कि मन, नक्शे के लिए आ सकते हैं लागू, विपक्ष के साथ एक सूची या Data.Sequence.Seq का निर्माण जबकि रैखिक समय है और यह हो सकता है ओ (एन) में बाइटस्टर्स या वैक्टर के साथ-साथ थोड़ी सी सोच के साथ लागू किया गया।

यह पता चला है कि इस तरह के वर्ग की उपयोगिता वास्तविक से अधिक सतही है।

मैं यह नहीं कह रहा हूँ कि एक अच्छा डिजाइन नहीं पाया जा सकता है, लेकिन इस तरह की डिजाइन का उपयोग करने और के लिए अनुकूलन करने के लिए मुश्किल होगा और संभावना डिजाइन की एक प्रयोग करने योग्य संस्करण हास्केल 98.

जा रहा है हवा नहीं होता

मैंने अपने कुंजी पैकेज में इस डिज़ाइन स्पेस के हिस्सों को निकाला है, जो कंटेनर इत्यादि में अनुक्रमणित करने के लिए बहुत सारे फ़ंक्शन प्रदान करता है, लेकिन मैंने जानबूझकर एक सूची जैसी एपीआई प्रदान करने से बचा है।) क्योंकि यह किया गया है कम सफलता से पहले और बी।) उपरोक्त विषम चिंताओं के कारण।

टीएल; डी अंतर्निहित संचालन के एसिम्प्टोटिक्स बदलते समय आप आम तौर पर एल्गोरिदम को बहुत अलग करना चाहते हैं।

Answer 6

दो प्रकार के वर्ग हैं जिन्हें Foldable और Traversable कहा जाता है जिसका उद्देश्य सूचियों और अन्य अनुक्रमिक डेटा संरचनाओं के कुछ सामान्य 1 व्यवहारों को अमूर्त करना है। हालांकि सभी डेटा संरचनाओं में इनके उदाहरण नहीं हैं, और मुझे नहीं पता कि वे संकलक के लिए पर्याप्त पारदर्शी हैं या नहीं, क्योंकि यह अभी भी उन पर अनुकूलन कर सकता है (क्या किसी को इसके बारे में कुछ पता है?)

स्रोत: Foldable and Traversable
भी देखें Why is Haskell missing “obvious” Typeclasses