带有kind的类型类型的实例的类型参数约束* - > * [英] Type parameters constraints for instances of typeclasses with kind * -> *

问题描述

假设我有 heap a 类型，其中 Heap 是类型为的类型构造函数。 > * 。堆上的许多基本操作要求 a 类型为 Ord 类型类的实例。

 数据堆a = ... 
 
 findMin :: Ord a =>堆a  - > a 
 deleteMin :: Ord a =>堆a  - > heap a 
  

我想声明我的 Heap 键入作为 Foldable 类型的实例，只要 a 类型参数是 Ord type类（通过 findMin 和 deleteMin 函数可以很容易地表达）。



当我们处理需要类型类型 * 的类型类时，可以轻松地表达这种关系，就像显示：

 实例Show a =>显示（堆a）其中
显示h = ... 
  

但我遇到问题声明可折叠：

 实例可折叠堆其中
  -  -  Ouch，没有`a`类型的参数来限制！ 
 foldr fzh = ... 
  

是否可以对 a 类型参数在这样的实例声明中？

解决方案

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


有时这是一个烦恼，而最常见的例子确实需要一个有序的数据结构的 Ord 约束，否则该数据结构可能是一个很好的，行为良好的实例。

有一些涉及类似约束类的东西的实验技术，但在您的具体情况下，已经有一个可行的解决方案。如果你看看 Foldable 的定义，它表示只有 foldMap 或 foldr 需要实施，所以我们会考虑这些。注意类型：



  foldMap ::（可折叠t，Monoid m）=> （a  - > m） - > t a  - > m 
 foldr ::（可折叠t）=> （a  - > b  - > b） - > b  - > t a  - > b 
  

在这两种情况下，使用可折叠实例只出现一次，作为函数的参数。因此，您可以使用GADT 用 Ord 约束：



 数据Heap a where 
 Heap ::（Ord a）=> ... 
  

通过这样做，您需要一个 Ord instance在任何时候创建 a Heap 值，甚至是一个空的堆;但是当你收到一个 Heap 值时，它的模式匹配会带来 Ord 实例回到范围 - 甚至在 Foldable 实例中！

请注意，在许多其他情况下：

  fmap ::（Functor f）=> （a  - > b） - > f a  - > fb 
  

这里我们可以得到一个 Ord 实例在 a 上，但我们还需要一个用于 b ，这是不可能的。

  return ::（Monad m）=> a  - > ma 
  

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

Suppose I have Heap a type where Heap is type constructor of kind * -> *. Many basic operations on heap require the a type to be an instance of Ord type class.

data Heap a = ...

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

I want to declare my Heap type as an instance of Foldable type class as soon as a type parameter is an instance of Ord type class (it will be easy to express via findMin and deleteMin functions).

This kind of relation can be easely expressed when we dealing with type classes that require type of kind *, like Show:

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

But I have problems with declaration of Foldable:

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

Is it possible to put constraint on a type parameter in such instance declaration?

解决方案

In general, no, when the type constructor itself is given the instance, there's no way to constrain the types it's applied to. Mostly this is a good thing, since it ensures that e.g. Functor instances are truly agnostic about their element type, which helps keep nice and predictable behavior nice and predictable.

Sometimes it's an annoyance instead, and the most common example is indeed needing an Ord constraint for a sorted data structure that could otherwise be a nice, well-behaved instance.

There are some experimental techniques involving stuff like constraint kinds, but in your specific case there's already a viable solution. If you look at the definition of Foldable, it says that only foldMap or foldr need to be implemented, so we'll consider those. Note the types:

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

In both cases, the type with a Foldable instance only appears once, as an argument to the function. Because of this, you can use GADTs with an Ord constraint:

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

By doing this, you'll need an Ord instance any time you create a Heap value, even an empty heap; but when you receive a Heap value, pattern matching on it will bring the Ord instance back into scope--even inside the Foldable instance!

Note that this doesn't help in many other situations:

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

Here we can get an Ord instance on a, but we'd also need one for b, which isn't possible.

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

Here we need to provide an Ord instance as well.

这篇关于带有kind的类型类型的实例的类型参数约束* - > *的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！