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

Question

我正在尝试Set在Haskell中实现一个简单的操作,并且如何为它包含的元素表达类约束.

该Set类型的类是相当简单:

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

a的简单实现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

实现Setfor 的实例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有一个带有附加Ord约束的map函数:

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
  ...

以下是Dominic Orchard 的博客文章,其中更详细地解释了这些想法.