Могу ли я параметризировать пустой тип ограничения?

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 -> *, который вызывает ошибку типа.

Если вы не хотите использовать пользовательский класс, вы можете попробовать, например, Const (Eq ()) или же Const (Num Int), которые имеют правильный вид k2 -> Constraint, Однако я не рекомендую этого, поскольку считаю, что он менее читабелен, чем использование пользовательского класса.

(Это требует включения некоторых расширений, как Бенджамин Ходжсон указывает ниже в комментарии.)