Реализация заказа через хеширование

Question

У меня есть относительно большой набор алгебраических c типов данных, где я не могу автоматически получить Eq и Ord, потому что одно поле в типе данных считается метаданными и не должно рассматриваться в равенстве и упорядоченность. Например, тип данных может выглядеть следующим образом:

data Foo = A Int | B String | C String Int | ... | Z String String Int 

Где каждый Int в этом случае является метаданными.

Итак, что я делаю, это вручную реализую Eq, просто сравнивая конструкторы. Но для Ord это становится безумием, потому что если у меня есть n конструкторы, я должен реализовать n^2 функции сравнения. Поэтому в настоящее время моя работа заключается в том, чтобы вручную реализовать Hashable, что требует от меня реализации единственной функции ha sh для каждого конструктора. А затем просто выполните сравнение ha sh в моем экземпляре Ord.

Очевидно, что здесь есть некоторые проблемы, поскольку compare (hash x) (hash y) == EQ -> x == y не выполняется, поскольку два разных значения могут иметь одинаковое значение ha sh. Однако это можно сделать, сначала проверив равенство вручную, и в этом случае всегда говорите, что левая сторона меньше, чем правая.

Однако теперь у вас есть это для некоторых значений любого типа: a < b && b < a. Но я не уверен, что это разрешено в экземпляре Haskell Ord. Так что, в основном, мой вопрос, является ли это Оке для реализации Ord, как это или нет? Мне нужна Ord, потому что многие библиотеки требуют Ord. Например, библиотеки графов и библиотеки карт.

Вот полный пример:

{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE ViewPatterns #-}

module Test where

import Prelude

import Data.Bits (xor)
import Data.Hashable (Hashable (..))

data Foo = A Int | B String | C String Int | Z String String Int

instance Eq Foo where
    (A _) == (A _)             = True
    (B x1) == (B x2)           = x1 == x2
    (C x1 _) == (C x2 _)       = x1 == x2
    (Z x1 y1 _) == (Z x2 y2 _) = x1 == x2 && y1 == y2
    _ == _                     = False

instance Hashable Foo where
    hashWithSalt s (A _)     = s `xor` (hash @Int 1)
    hashWithSalt s (B x)     = s `xor` (hash @Int 2) `xor` (hash x)
    hashWithSalt s (C x _)   = s `xor` (hash @Int 3) `xor` (hash x)
    hashWithSalt s (Z x y _) = s `xor` (hash @Int 4) `xor` (hash x) `xor` (hash y)

instance Ord Foo where
    compare (hash -> a) (hash -> b) = case compare a b of
                                        EQ -> if a == b then EQ else LT
                                        e -> e

Answer 1

Ну, это оказалось немного сложнее, чем я ожидал, когда я на самом деле все это написал, так что, возможно, кто-то может придумать что-нибудь попроще, но ...

Если у вас есть свобода изменив ваши типы, я бы предложил сделать ваш тип polymorphi c в целочисленном типе с ошибкой и получить функтор:

{-# LANGUAGE DeriveFunctor #-}
data FooF int = A int | B String | C String int | Z String String int deriving (Functor)

Теперь ваш исходный тип задается псевдонимом:

type Foo = FooF Int

Вы можете использовать автономное предложение для получения Eq и Ord для FooF ():

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE StandaloneDeriving #-}
deriving instance Eq (FooF ())
deriving instance Ord (FooF ())

, а затем с функцией преобразования, которая забывает целые числа:

forgetInts :: Foo -> FooF ()
forgetInts x = () <$ x

вы можете написать Foo экземпляров следующим образом:

import Data.Function
instance Eq Foo where
  (==) = (==) `on` forgetInts
instance Ord Foo where
  compare = compare `on` forgetInts

Один недостаток состоит в том, что вам могут потребоваться дополнительные подписи или аннотации типов, поскольку A 10 больше не является однозначно FooF Int в отличие от FooF Double. См., Например, main ниже.

Полный код:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE StandaloneDeriving #-}

import Data.Function

data FooF int = A int | B String | C String int | Z String String int deriving (Functor)
type Foo = FooF Int
deriving instance Eq (FooF ())
deriving instance Ord (FooF ())

forgetInts :: Foo -> FooF ()
forgetInts x = () <$ x

instance Eq Foo where
  (==) = (==) `on` forgetInts
instance Ord Foo where
  compare = compare `on` forgetInts

main = do
  print $ Z "foo" "bar" 1 == (Z "foo" "bar" 2 :: Foo)
  print $ compare (A 10) (A 20 :: Foo)

Answer 2

Вот решение без хэширования, которое может работать, даже если у вас несколько типов метаданных (где ответ Functor, который я написал отдельно, не работает). Если у вас есть возможность обернуть свои метаданные в newtype, вы можете использовать экземпляры Eq и Ord для нового типа, чтобы "экранировать" метаданные от производных Eq и Ord:

-- Meta data is always equal
newtype Meta a = Meta a
instance Eq (Meta a) where
  x == y = True
  x /= y = False
instance Ord (Meta a) where
  compare x y = EQ

Затем тип, подобный:

data Foo = A (Meta Int) | B String | C String (Meta Bool) 
  | Z String String (Meta String) deriving (Eq, Ord)

с производными экземплярами Eq и Ord, сравнивается, как если бы метаданных там не было:

main = do
  print $ Z "foo" "bar" (Meta "different") == Z "foo" "bar" (Meta "but still the same")
  print $ compare (A (Meta 10)) (A (Meta 20))

Здесь недостатком является обычная проблема с упаковщиками нового типа: вам нужно обернуть и развернуть (или coerce) метаданные.

Полный код:

newtype Meta a = Meta a
instance Eq (Meta a) where
  x == y = True
  x /= y = False
instance Ord (Meta a) where
  compare x y = EQ

data Foo = A (Meta Int) | B String | C String (Meta Bool)
  | Z String String (Meta String) deriving (Eq, Ord)

main = do
  print $ Z "foo" "bar" (Meta "different") == Z "foo" "bar" (Meta "but still the same")
  print $ compare (A (Meta 10)) (A (Meta 20))