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

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

data Heap a = ... 

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

我想尽快a类型参数Ord类型的类的实例声明我Heap类型Foldable型类的一个实例（它会很容易通过findMin和deleteMin函数来表示）。

这种关系可当我们需要的那种*类型类型类，处理像Show被easely表示：

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类型参数设置约束？

来源

2012-09-19 roman-kashitsyn

看看[这个东西]（http://blog.omega-prime.co.uk/?p=127）。他们正在做一些与monads类似的事情。 – phg

非常感谢您的链接，'ConstraintKind'是_really_有趣的东西！ –

顺便说一句，'findMin'真的需要一个'Ord'实例吗？ – yairchu

一般来说，不，在给类型构造函数本身赋予实例时，没有办法约束它应用到的类型。大多数情况下这是一件好事，因为它确保了例如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实例的类型只出现一次，作为参数传递给函数。正因为如此，你可以use GADTs与Ord约束：

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

通过这样做，你需要一个Ord比如你创建一个Heap值，即使是空堆的任何时间;但是当您的接收到 a Heap值时，其上的模式匹配将使Ord实例回到范围内 - 即使在Foldable实例内！

请注意，这并不在许多其他情况下帮助：

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

在这里，我们可以a得到Ord实例，但我们也需要愿意为一个b，这是不可能的。

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

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

来源

2012-09-19 16:41:22

谢谢，我知道它的工作原理，我准备了一个小样本，在这里如何做到这一点：http://ideone.com/HWl7H。对我来说这看起来很奇怪，但我们不能像这样在类型声明中使用约束：'newtype Ord a => ListHeap a = LH [a]'。这只是'可折叠'实例不工作。我们确实必须使用模式匹配的GADT扩展。非常感谢您的回答！ –

@ roman-kashitsyn：是的，对于常规数据类型，有/是一种类似的语法，但它没有做同样的事情，并且是完全无用的错误特征，最终可能会从语言标准中删除（除非它已经当时我已经忘记了）。 –

看看在Hackage上的keys图书馆。检查它的FoldableWithKey类型类是否是你需要的。

来源

2012-09-19 22:26:28 nponeccop

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

回答

相关问题