使用不同的集合排序

Question

我正在阅读纯功能数据结构的第2章,其中讨论了作为二叉搜索树实现的无序集.代码用ML编写,最后显示a signature ORDERED和a 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有时候很烦人,但你会得到一些好处:

• 当你看到a 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结果比你期望的更容易组合.例如,ReverseInt您所创建的类型已经存在于一种形式,该形式通用于反转具有约束的任何类型Ord:它被调用Down.为了明确,您可以使用Down Int而不是ReversedInt,并获得您免费写出的实例!

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

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

然后,每次你创建一个Set,你必须传入比较键.