haskell - 类型参数约束类型类实例的类型 * -> *

Question

假设我有Heap atype where Heapis type constructor of kind * -> *。堆上的许多基本操作都要求a类型是Ord类型类的实例。

data Heap a = ...

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

一旦类型参数是类型类的实例，我想将我的类型声明Heap为类型类的实例（通过和函数很容易表达）。FoldableaOrdfindMindeleteMin

当我们处理需要 kind 类型的类型类时，这种关系可以很容易地表达出来*，例如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是否可以在此类实例声明中对类型参数施加约束？

score 18 · Accepted Answer

一般来说，不，当类型构造函数本身被赋予实例时，没有办法约束它应用到的类型。大多数情况下这是一件好事，因为它确保了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实例的类型只出现一次，作为函数的参数。因此，您可以使用带有约束的GADTOrd：

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

通过这样做，您在Ord任何时候创建一个Heap值时都需要一个实例，甚至是一个空堆；但是当您收到一个Heap值时，对其进行模式匹配会将Ord实例带回范围 - 甚至在Foldable实例内部！

请注意，这在许多其他情况下无济于事：

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

在这里，我们可以获得一个Ordon 的实例a，但我们还需要一个 for b，这是不可能的。

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

这里我们也需要提供一个Ord实例。

score 0 · Accepted Answer

0

看看keys关于 Hackage 的图书馆。检查它的FoldableWithKey类型类是否是您需要的。

于 2012-09-19T22:26:28.833 回答

2 回答 2