haskell - 在 Haskell 中实现类型类时的任意类约束

Question

我正在尝试实现一个简单的 Set在 Haskell 中，并且我对如何表达它包含的元素的类约束感到困惑。
Set type 类相当简单:

class Set s where
  empty    :: s a
  isEmpty  :: s a -> Bool
  insert   :: s a -> a -> s a
  contains :: s a -> a -> Bool

Set 的简单实现是二叉搜索树:

data BinarySearchTree a = Node a (BinarySearchTree a) (BinarySearchTree a) | Leaf

但是，在声明正确的类约束时，我有点卡住了:

Set至少需要确定两个元素是否相等的能力——它的值需要有一个 Eq 的实例。 .

BinarySearchTree要求其元素具有 Ord 的实例，因为每个节点都需要左侧较小的元素和右侧较大的元素。

第一个简单的解决方案是更新 Set的签名要求 a有一个 Eq 的实例:

class Set s where
  empty    :: Eq a => s a
  isEmpty  :: Eq a => s a -> Bool
  insert   :: Eq a => s a -> a -> s a
  contains :: Eq a => s a -> a -> Bool

实现 Set 的实例为 BinarySearchTree不是问题:Ord暗示 Eq ，所以我可以“覆盖”类约束。

但是，如果 BinarySearchTree需要一些奇特的类约束，这些约束与 Eq 完全不兼容。 ?我如何表达这些并让类型检查器满意？

我能想到的唯一方法是在 BinarySearchTree 上添加类约束， 就像是:

data Ord a => BinarySearchTree a = Node a (BinarySearchTree a) (BinarySearchTree a) | Leaf

不幸的是，这似乎不能满足类型检查器:即使声明保证 BinarySearchTree必须包含带有 Ord 的元素例如，这个约束似乎没有延续到使用 BinarySearchTree 的函数。 - 就好像类约束只应用于数据构造函数，但后来被遗忘了。

我错过了什么？我正在尝试做的事情是否有一个优雅的解决方案，甚至根本没有解决方案？

Answer 1

您正在询问 Haskell 中的一个众所周知的问题:如何定义类型类，以便类型类的实例可以定义类型类操作所需的类型类约束。这个问题经常以问题“为什么 Data.Set 不是 Functor 的实例？”的形式出现在论坛上。然后问题是Data.Set有一个 map 功能，附加 Ord约束:

Data.Set.map :: Ord b => (a -> b) -> Set a -> Set b 

而 Functor 的 fmap 方法看起来像

class Functor f where
  fmap :: (a -> b) -> f a -> f b

几年以来，问题的解决方案已经存在。一种解决方案将相对较新的扩展 ConstraintKinds 与 TypeFamilies 相结合。对于您的示例，它相当于这样:

class Set s where
  type SetCt s a :: Constraint
  empty    :: s a
  isEmpty  :: s a -> Bool
  insert   :: Ct a => s a -> a -> s a
  contains :: Ct a => s a -> a -> Bool

BinarySearchTree 的实例看起来像

instance Set BinarySearchTree where
  type SetCt BinarySearchTree a = Ord a
  ...

这是一个 blog post作者 Dominic Orchard 更详细地解释了这些想法。