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

Question

我有一个队列类,它允许实例定义它对元素的约束.例如,优先级队列要求其元素可订购:

{-# 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总是可以出院.此外,由于该类中没有成员,因此它应该具有零(或几乎为零)的运行时成本.

()您尝试使用的"约束" 不被视为GHC设置的空约束,而是单元类型() :: *.这会导致Const () :: k2 -> *触发类型错误.

如果您不想使用自定义类,您可以尝试使用eg Const (Eq ())或者Const (Num Int)哪种类型k2 -> Constraint.不过,我不建议这样做,因为我发现它比使用自定义类更不易读.

(这需要启用一些扩展,正如Benjamin Hodgson在评论中指出的那样.)