असंगत ईक और ऑर्ड उदाहरण?

Question

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

instance Eq BigThing where 
(==) b b' = name b == name b' && 
      firstPart b == firstPart b' && 
      secondPart b == secondPart b' && 
      {- ...and so on... -} 

instance Ord BigThing where 
compare b b' = compare (name b) (name b') 

लेकिन नाम के बाद से हमेशा अलग वस्तुओं के लिए अलग नहीं किया जा सकता है, इस उत्सुक मामले में जहां दो BigThings == के अनुसार inequal हो सकता है जोखिम है, लेकिन की तुलना उन EQ अर्जित करता है।

क्या यह हास्केल पुस्तकालयों के साथ समस्याएं पैदा करेगा? क्या एक और तरीका है कि मैं एक विस्तृत समानता संचालन के लिए आवश्यकता को पूरा कर सकता हूं लेकिन एक सस्ता आदेश?

Answer 1

पहले, Text या String के बजाय ByteString का उपयोग कर कुछ और बदले बिना एक बहुत मदद कर सकता है।

आम तौर पर Ord के साथ असंगत उदाहरण बनाने की अनुशंसा नहीं करता। पुस्तकालय सही ढंग से इस पर निर्भर हो सकते हैं, और आप कभी नहीं जानते कि यह किस तरह की अजीब समस्याएं पैदा कर सकता है। (उदाहरण के लिए, आप कर रहे हैं यकीन कि MapEq और Ord के बीच संबंध का उपयोग नहीं करता?)

---

आप बिल्कुल Eq उदाहरण की जरूरत नहीं है, तो आप बस को परिभाषित कर सकते

instance Eq BigThing where 
    x == y = compare x y == EQ 

फिर समानता तुलना के अनुरूप होगी। ऐसी कोई आवश्यकता नहीं है कि बराबर मानों में सभी फ़ील्ड बराबर हों।

---

आप एक Eq उदाहरण है कि सभी क्षेत्रों तुलना की जरूरत है, तो आप एक newtype में BigThing लपेटकर द्वारा लगातार रह सकते हैं इसके बाद के संस्करण Eq और Ord इसके लिए परिभाषित करते हैं, और अपने एल्गोरिथ्म में इसका इस्तेमाल करते हैं जब भी आप की जरूरत है आदेश देने अनुसार name रहे हैं:

newtype BigThing' a b c = BigThing' (BigThing a b c) 
instance Eq BigThing' where 
    x == y = compare x y == EQ 
instance Ord BigThing' where 
    compare (BigThing b) (BigThing b') = compare (name b) (name b') 

---

अद्यतन: के बाद से आप कहते हैं कि किसी भी आदेश स्वीकार्य है, आप ca अपने लाभ के लिए हैशिंग का उपयोग करें। इसके लिए, आप hashable पैकेज का उपयोग कर सकते हैं। विचार यह है कि आप डेटा निर्माण पर हैश मानों की पूर्व-गणना करते हैं और मानों की तुलना करते समय उनका उपयोग करते हैं। यदि दो मान अलग हैं, तो यह लगभग निश्चित है कि उनके हैंश अलग होंगे और आप केवल उनके हैंश (दो पूर्णांक) की तुलना करेंगे, और कुछ भी नहीं। यह ऐसा दिखाई दे सकता:

module BigThing 
    (BigThing() 
    , bigThing 
    , btHash, btName, btSurname 
    ) 
where 

import Data.Hashable 

data BigThing = BigThing { btHash :: Int, 
          btName :: String, 
          btSurname :: String } -- etc 
    deriving (Eq, Ord) 
-- Since the derived Eq/Ord instances compare fields lexicographically and 
-- btHash is the first, they'll compare the hash first and continue with the 
-- other fields only if the hashes are equal. 
-- See http://www.haskell.org/onlinereport/derived.html#sect10.1 
-- 
-- Alternativelly, you can create similar Eq/Ord instances yourself, if for any 
-- reason you don't want the hash to be the first field. 

-- A smart constructor for creating instances. Your module will not export the 
-- BigThing constructor, it will export this function instead: 
bigThing :: String -> String -> BigThing 
bigThing nm snm = BigThing (hash (nm, snm)) nm snm 

ध्यान दें कि यह समाधान के साथ, आदेश क्षेत्रों के लिए कोई स्पष्ट संबंध के साथ मालूम होता है यादृच्छिक किया जाएगा।

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

module HashOrd 
    (Hashed() 
    , getHashed 
    , hashedHash 
    ) 
where 

import Data.Hashable 

data Hashed a = Hashed { hashedHash :: Int, getHashed :: a } 
    deriving (Ord, Eq, Show, Read, Bounded) 

hashed :: (Hashable a) => a -> Hashed a 
hashed x = Hashed (hash x) x 

instance Hashable a => Hashable (Hashed a) where 
    hashWithSalt salt (Hashed _ x) = hashWithSalt salt x