haskell - 通过散列实现排序

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 .例如图形库和 map 库。

这是一个完整的例子:

{-# 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)