कैसे श्रेणी उदाहरण के लिए समानता को परिभाषित करने के?

Question

आदेश उदाहरण डेटा प्रकार पर कुछ कार्यों के लिए श्रेणी कानूनों पकड़ के लिए यह साबित करने के लिए, एक कैसे तय करते हैं कि कैसे समानता परिभाषित करने के लिए? का प्रतिनिधित्व बूलियन अभिव्यक्ति के लिए निम्न प्रकार को ध्यान में रखते:

data Exp 
    = ETrue 
    | EFalse 
    | EAnd Exp Exp 
    deriving (Eq) 

यह संभव साबित करने के लिए कोशिश कर रहा है कि ऍक्स्प रूपों पहचान ETrue और ऑपरेटर के साथ एक श्रेणी:

(<&>) = EAnd 

Eq को पुनर्परिभाषित बिना उदाहरण? यानी का डिफ़ॉल्ट उदाहरण का उपयोग करते हुए Eqबाएं पहचान कानून टूटता है,:

ETrue <&> e == e 

झूठी मूल्यांकन करता है।

eval ETrue = True 
eval EFalse = False 
eval (EAnd e1 e2) = eval e1 && eval e2 

और के रूप में Eq उदाहरण:

instance Eq Exp where 
    e1 == e2 = eval e1 == eval e2 

समस्या ठीक करता है हालांकि, एक eval समारोह को परिभाषित। ऐसे कानूनों को पूरा करने के दावा करने के लिए (==) सामान्य आवश्यकता के संदर्भ में तुलना है, या यह कहना है कि कानून समानता ऑपरेटर की एक विशेष प्रकार के लिए पकड़ के लिए पर्याप्त है?

Answer 1

समानता EVIL है। आप शायद ही कभी (यदि कभी) की जरूरत है संरचनात्मक समानता, क्योंकि यह भी मजबूत है। आप केवल एक तुल्यता कि के लिए पर्याप्तमजबूत आप क्या कर रहे है चाहता हूँ। इस के लिए श्रेणी के सिद्धांत विशेष रूप से सच है।

हास्केल में, deriving Eq आप संरचनात्मक समानता, जिसका अर्थ है कि आप अक्सर ==//= का अपना स्वयं का कार्यान्वयन लिखना चाहें दे देंगे।

एक साधारण उदाहरण: पूर्णांक के जोड़े के रूप में तर्कसंगत संख्या को परिभाषित करें, data Rat = Integer :/ Integer। आप संरचनात्मक समानता (क्या हास्केल deriving है) का उपयोग करते हैं, तो आप (1:/2) /= (2:/4) है, लेकिन एक अंश के रूप में 1/2 == 2/4 करेंगे। आपको वास्तव में यह मानना ​​है कि आपके tuples को इंगित करते हैं, उनके प्रतिनिधित्व नहीं। इसका मतलब है कि आपको समकक्ष की आवश्यकता होगी जो घटाए से कम है, इसलिए आपको इसे लागू करना चाहिए।

साइड नोट: कोड का उपयोग कर किसी मानता है कि आप एक संरचनात्मक समानता परीक्षण है, यानी कि == को सही ठहराते पैटर्न मिलान के माध्यम से डाटा उप घटकों की जगह के साथ की जाँच के द्वारा निर्धारित किए गए हैं, उनके कोड टूट सकता है।यदि यह महत्वपूर्ण है, आप रचनाकारों को पैटर्न मिलान को अस्वीकार करने के लिए छिपा सकते हैं, या शायद अपने class (कहें, Equiv=== और =/= के साथ) दोनों अवधारणाओं को अलग करने के लिए परिभाषित कर सकते हैं। (यह ज्यादातर AGDA या Coq तरह प्रमेय Provers के लिए महत्वपूर्ण है, हास्केल में यह व्यावहारिक/वास्तविक दुनिया कोड तो गलत है कि अंत में कुछ टूट जाता है पाने के लिए वास्तव में मुश्किल है।)

सच बेवकूफ (टीएम) उदाहरण: चलो मान लें कि व्यक्ति विशाल Rat एस की लंबी सूचियों को मुद्रित करना चाहता है और Integer एस के स्ट्रिंग प्रस्तुतियों को याद रखने का मानना ​​है कि बाइनरी-टू-दशमलव रूपांतरण पर बचाएगा। Rat एस के लिए एक लुकअप टेबल है, जैसे कि Rat एस को दो बार परिवर्तित नहीं किया जाएगा, और पूर्णांक के लिए एक लुकअप टेबल है। यदि (a:/b) == (c:/d), गुम पूर्णांक प्रविष्टियों को a - c/ b - d रूपांतरण को छोड़ने के लिए प्रतिलिपि करके भर दिया जाएगा (ouch!)। सूची [ 1:/1, 2:/2, 2:/4 ], 1 परिवर्तित हो जाती है और फिर, 1:/1 == 2:/2, 1 के लिए स्ट्रिंग 2 लुकअप प्रविष्टि में कॉपी हो जाती है। अंतिम परिणाम "1/1, 1/1, 1/4" बर्क किया गया है।