4

我有一组相对较大的代数数据类型，我无法自动派生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。我不确定在 HaskellOrd实例中是否允许。所以基本上我的问题是这样实施 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
4

2 回答 2

4

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

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

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

现在，您的原始类型由别名给出：

type Foo = FooF Int

您可以使用独立的派生子句来派生Eq和Ordfor 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)
于 2020-04-24T18:55:48.470 回答
1

这是一个无哈希的解决方案，即使您有多种元数据类型也可能有效（Functor我单独发布的答案不起作用）。如果您可以灵活地将元数据包装在 anewtype中，则可以使用newtype 的EqandOrd实例来“屏蔽”派生的Eqand元数据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))
于 2020-04-27T19:42:36.020 回答