haskell - 对集合使用不同的排序

Question

我正在阅读 Purely Functional Data Structures 的第 2 章，其中讨论了作为二叉搜索树实现的无序集。该代码是用 ML 编写的，最终显示 signature ORDERED和一个 functor UnbalancedSet(Element: ORDERED): SET .来自更多的 C++ 背景，这对我来说很有意义；自定义比较函数对象构成类型的一部分，可以在构造时传入，这似乎与 ML 仿函数的做事方式非常相似。

谈到 Haskell，似乎行为只取决于 Ord例如，如果我想要一个顺序颠倒的集合，似乎我必须使用 newtype实例，例如

newtype ReverseInt = ReverseInt Int deriving (Eq, Show)

instance Ord ReverseInt where
    compare (ReverseInt a) (ReverseInt b)  
        | a == b = EQ
        | a < b  = GT
        | a > b  = LT

然后我可以在一组中使用它:

let x = Set.fromList $ map ReverseInt [1..5]

有没有更好的方法来做这种事情而不诉诸使用 newtype创建一个不同的 Ord实例？

Answer 1

不，这真的是要走的路。是的，有一个 newtype有时很烦人，但你会得到一些很大的好处:

当您看到 Set a你知道a ，您立即知道它使用什么类型的比较(类似于纯度使代码更具可读性，而不需要跟踪执行)。你不必知道在哪里 Set a来自。

许多情况下，您可以 coerce 一次通过多个新类型的方式。比如我可以转xs = [1,2,3] :: Int进入 ys = [ReverseInt 1, ReverseInt 2, ReverseInt 3] :: [ReverseInt]只是使用 ys = coerce xs :: [ReverseInt] .不幸的是，Set 并非如此。 (并且它不应该 - 您需要强制转换函数是单调的，以免搞砸数据结构不变量，并且还没有一种方法可以在类型系统中表达它)。

newtype s 最终比您预期的更可组合。例如，ReverseInt您创建的类型已经以一种形式存在，该形式概括为使用 Ord 反转任何类型约束:它被称为 Down .明确地说，您可以使用 Down Int而不是 ReversedInt ，然后您就可以免费获得您写出的实例!

当然，如果您对此仍然感到非常强烈，那么没有什么可以阻止您编写 Set 的版本。它必须有一个字段，它是它使用的比较函数。就像是

data Set a = Set { comparisionKey :: a -> a -> Ordering
                 , ...
                 }

然后，每次做 Set ，您必须传入比较键。