Haskell Constraint не меньше, чем глава экземпляра

Некоторые кольца могут быть оснащены нормированной функцией:

class (Ring.C a) => EuclideanDomain a where
  norm :: a -> Integer

С помощью этой функции кольцо можно упорядочить очевидным образом:

compare x y = compare (norm x) (norm y)

Но я не уверен, как это указать. Я пытался сделать

instance (EuclideanDomain a, Eq a) => Ord a where

но это дает мне некоторые предупреждения, и когда я включаю соответствующие флаги компилятора, он говорит мне: "Ограничение не меньше, чем глава экземпляра" - если я включаю UndecidableInstances, все идет в ад.

Есть ли способ сделать то, что я хочу?

Ответ 1

hammar уже предоставил решение; Я хотел бы указать еще одну проблему с этим примером. То, что вы хотите выразить, - "Всякий раз, когда тип является экземпляром Eq и EuclideanDomain, используйте это правило, чтобы создать экземпляр для Ord." Но это невыразимо в Хаскелле. Строка

instance (EuclideanDomain a, Eq a) => Ord a where

на самом деле означает: "Используйте это правило для создания экземпляра Ord для любого типа. Это ошибка, если экземпляры EuclideanDomain и Eq не входят в область видимости". Это не хорошо, потому что это правило будет перекрываться с каждым другим экземпляром Ord.

В принципе, в любое время, когда вы хотите написать экземпляр Class typevar, вам понадобится новый тип.

Ответ 2

Чтобы избежать бесконечных циклов, компилятор обычно требует, чтобы ограничения экземпляра были "меньше", чем сам экземпляр, так что алгоритм завершится. Ваш экземпляр не делает меньше a в ограничениях, так что компилятор жалуется.

Расширение UndecidableInstances отменяет это ограничение, оставляя его до вас, чтобы доказать, что оно закончится. Таким образом, при использовании этого расширения можно отправить компилятор в бесконечный цикл.

Общим решением является добавление newtype:

newtype ByNorm a = ByNorm a

instance (EuclideanDomain a, Eq a) => Ord (ByNorm a) where
    compare (ByNorm x) (ByNorm y) = compare (norm x) (norm y)

Теперь ограничения меньше, чем головка экземпляра, поскольку они отделяют newtype. Не требуется расширение.