我可以参数化空约束类型吗？

Question

我有一个 class 队列，它允许实例定义它对元素的约束。例如，优先级队列要求其元素是可排序的：

{-# LANGUAGE MultiParamTypeClasses, ConstraintKinds, FunctionalDependencies #-}

class Queue q c | q -> c where
    empty :: q a
    qpop :: c a => q a -> Maybe (a, q a)
    qpush :: c a => a -> q a -> q a

data PriorityQueue a = ...

instance Queue PriorityQueue Ord where
    ...

这很有用：在 PriorityQueue 的实例声明中，我可以使用 Ord 的成员对队列元素进行操作，例如 (>).

我在尝试定义一个对其元素没有任何要求的队列时遇到了困难：

newtype LIFO a = LIFO [a]

instance Queue LIFO () where
    empty = LIFO []
    qpop (LIFO []) = Nothing
    qpop (LIFO (x:xs)) = Just (x, LIFO xs)
    qpush x (LIFO xs) = LIFO $ x:xs

失败，GHC 显示以下错误消息：

The second argument of `Queue' should have kind `* -> Constraint',
  but `()' has kind `*'
In the instance declaration for `Queue LIFO ()'

这条错误消息对我来说很有意义。 Eq 接受一个类型参数（我们通常写 Eq a => ...）而 () 没有参数——这是一个普通的旧类型不匹配。

我在编写忽略其第二个参数的类型函数时遇到了难题，这将允许我编写 instance Queue LIFO (Const ()):

{-# LANGUAGE TypeFamilies, KindSignatures, PolyKinds #-}

type family Const a b :: k -> k2 -> k
type instance Const a b = a

我觉得这种类型族和种类多态性的交互非常漂亮，所以当它不起作用时我很失望（我真的以为它会！）：

Expecting two more arguments to `a'
The first argument of `Const' should have kind `*',
  but `a' has kind `k0 -> k1 -> k0'
In the type `a'
In the type instance declaration for `Const'

我觉得最后一个例子有点像语法错误一样愚蠢（我是输入族的新手）。我怎样才能写一个不对其参数施加任何限制的 Constraint？

Answer 1

这应该有效：

class NoConstraint a where
instance NoConstraint a where

instance Queue LIFO NoConstraint where
  ...

上面定义了一个所有类型都满足的约束。因此，c a 中 c = NoConstraint 的义务始终可以解除。此外，由于 class 中没有任何成员，它的运行时间成本应该为零（或接近零）。

您尝试使用的 "constraint" () 不是 GHC 设置的空约束，而是单位类型 () :: *。这会导致 Const () :: k2 -> *，从而触发类型错误。

如果您不想使用自定义 class，您可以尝试例如Const (Eq ()) 或 Const (Num Int)，它们具有正确的种类 k2 -> Constraint。不过，我不推荐这样做，因为我发现它的可读性不如使用自定义 class.

（这需要启用一些扩展，正如 Benjamin Hodgson 在下面的评论中指出的那样。）

我可以参数化空约束类型吗？

Can I parameterise the empty constraint type?

haskell

typeclass

type-constraints

type-families