Các trường hợp Eq và Ord không nhất quán?

Question

Tôi có một chương trình Haskell lớn đang chạy chậm chạp. Profiling và thử nghiệm đã tiết lộ rằng một phần lớn thời gian là chi tiêu so sánh bình đẳng và thứ tự của một kiểu dữ liệu lớn cụ thể rất quan trọng. Bình đẳng là một hoạt động hữu ích (đây là tìm kiếm không gian trạng thái, và tìm kiếm đồ thị là thích hợp hơn nhiều với tìm kiếm cây), nhưng tôi chỉ cần một cá thể Ord cho lớp này để sử dụng Maps. Vì vậy, những gì tôi muốn làm là nói

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') 

Nhưng kể từ khi tên có thể không phải luôn luôn khác nhau cho các đối tượng khác nhau, điều này có nguy cơ trường hợp tò mò nơi hai BigThings có thể inequal theo ==, nhưng so sánh chúng mang lại EQ.

Điều này có gây ra sự cố với thư viện Haskell không? Có cách nào khác tôi có thể đáp ứng các yêu cầu cho một hoạt động bình đẳng chi tiết nhưng một thứ tự giá rẻ?

Answer 1

Thứ nhất, sử dụng Text hoặc ByteString thay vì String có thể giúp rất nhiều mà không thay đổi bất cứ điều gì khác.

Nói chung tôi không khuyên bạn nên tạo một phiên bản Eq không phù hợp với Ord. Thư viện có thể phụ thuộc một cách hợp lý vào nó, và bạn không bao giờ biết những vấn đề kỳ lạ nào nó có thể gây ra. (Ví dụ, bạn có chắc chắn rằng Map không sử dụng mối quan hệ giữa Eq và Ord?)

---

Nếu bạn không cần dụ Eq ở tất cả, bạn chỉ có thể xác định

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

Sau đó, sự bình đẳng sẽ nhất quán với so sánh. Không có yêu cầu rằng các giá trị bằng nhau phải có tất cả các trường bằng nhau.

---

Nếu bạn cần một thể hiện Eq so sánh tất cả các lĩnh vực, sau đó bạn có thể ở lại phù hợp bằng cách gói BigThing thành một newtype, xác định trên Eq và Ord cho nó, và sử dụng nó trong thuật toán của bạn bất cứ khi nào bạn cần đặt hàng theo để 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') 

---

cập nhật: Vì bạn nói bất kỳ trật tự là chấp nhận được, bạn ca n sử dụng băm để lợi thế của bạn. Đối với điều này, bạn có thể sử dụng gói hashable. Ý tưởng là bạn tính toán trước các giá trị băm khi tạo dữ liệu và sử dụng chúng khi so sánh các giá trị. Nếu hai giá trị khác nhau, nó gần như chắc chắn rằng các hash của chúng sẽ khác nhau và bạn chỉ so sánh các hash của chúng (hai số nguyên), không gì hơn. Nó có thể trông giống như sau:

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 

Lưu ý rằng với giải pháp này, thứ tự dường như là ngẫu nhiên không có mối liên hệ rõ ràng với trường.

Bạn cũng có thể kết hợp giải pháp này với giải pháp trước đó. Hoặc, bạn có thể tạo một mô-đun nhỏ để gói bất kỳ loại nào với giá trị băm được tính trước của nó (giá trị được bao bọc phải có các trường hợp Eq phù hợp với các phiên bản Hashable của chúng).

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