通过散列实现排序

Question

我有一组相对较大的代数数据类型，我无法自动派生 Eq 和 Ord，因为数据类型中的单个字段被视为元数据，不应被考虑在平等和有序。例如，数据类型可能如下所示：

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

在这种情况下，每个 Int 都是元数据。

所以我所做的是通过比较构造函数手动实现 Eq。但是对于 Ord 这变得疯狂，因为如果我有 n 构造函数，我必须实现 n^2 比较函数。所以目前我的工作是手动实现 Hashable 这需要我为每个构造函数实现一个散列函数。然后在我的 Ord 实例中进行哈希比较。

这显然有一些问题，因为 compare (hash x) (hash y) == EQ -> x == y 不成立，因为两个不同的值可以共享相同的散列。然而，这可以通过首先手动检查是否相等来处理，如果是这种情况，总是说左侧比右侧小。

但是现在对于任何类型的某些值，它都持有 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

好吧，这比我实际写出来时预期的要复杂一些，所以也许有人可以想出更简单的东西，但是...

如果您可以自由地修改您的类型，我建议您在有问题的整数类型中使您的类型多态并派生一个仿函数：

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

现在，您的原始类型由别名指定：

type Foo = FooF Int

您可以使用独立的派生子句为 FooF () 派生 Eq 和 Ord:

{-# 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 新类型的实例到 "shield" 来自派生 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))

通过散列实现排序

Implement Ordering via hashing

haskell

partial-ordering