为类型为* - >*的类型类的实例键入参数约束

Question

假设我有Heap a类型Heap的类型构造函数* -> *.堆上的许多基本操作都要求a类型是Ord类类的实例.

data Heap a = ...

findMin :: Ord a => Heap a -> a
deleteMin :: Ord a => Heap a -> Heap a

我想将Heap类型声明为Foldable类型类的实例,只要a类型参数是Ord类型类的实例(它将很容易表达通过findMin和deleteMin函数).

当我们处理需要类型的类型类时,可以很容易地表达这种关系*,例如Show:

instance Show a => Show (Heap a) where
    show h = ...

但是我在申报时遇到了问题Foldable:

instance Foldable Heap where
    -- Ouch, there is no `a` type parameter to put the constraint on!
    foldr f z h = ...

是否可以a在此类实例声明中对类型参数设置约束？

Answer 1

通常,不,当类型构造函数本身被赋予实例时,没有办法约束它应用的类型.大多数情况下这是一件好事,因为它确保了例如Functor实例对其元素类型的真正不可知,这有助于保持良好和可预测的良好和可预测的行为.

有时它反而是烦恼,而最常见的例子确实需要Ord一个排序数据结构的约束,否则它可能是一个很好的,表现良好的实例.

有一些实验技术涉及约束类型之类的东西,但在您的具体情况下,已经有一个可行的解决方案.如果你看一下Foldable它的定义,它说只是foldMap或者foldr需要实现,所以我们会考虑那些.注意类型:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b

在这两种情况下,具有Foldable实例的类型仅出现一次,作为函数的参数.因此,您可以使用具有Ord约束的GADT:

data Heap a where
    Heap :: (Ord a) => ...

通过这样做,你需要一个Ord情况下,你任何时候创建一个Heap值,即使是空的堆; 但是当你收到一个Heap值时,它上面的模式匹配会把Ord实例带回范围 - 甚至在Foldable实例中!

请注意,这在许多其他情况下没有帮助:

fmap :: (Functor f) => (a -> b) -> f a -> f b

在这里我们可以得到一个Ord实例a,但我们也需要一个实例b,这是不可能的.

return :: (Monad m) => a -> m a

这里我们还需要提供一个Ord实例.