Haskell restricción es no menor que la cabeza ejemplo

Question

Algunos anillos pueden estar equipados con una función de norma:

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

Con esta función, el anillo puede ser ordenado en la manera obvia:

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

Pero no estoy seguro de cómo indicar esto. He intentado hacer

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

pero esto me da algunas advertencias, y cuando activo las opciones del compilador pertinentes me dice "restricción no es menor que la cabeza instancia" - si habilito UndecidableInstances todo va al infierno.

¿Hay alguna manera de hacer lo que quiero?

Answer 1

Para evitar bucles infinitos, el compilador normalmente requiere que las restricciones de una instancia sean "más pequeñas" que la propia instancia, de modo que el algoritmo terminará. Su instancia no hace que a sea más pequeño en las restricciones, por lo que el compilador se queja de eso.

La extensión UndecidableInstances levanta esta restricción, dejando que usted demuestre que terminará. De este modo, es posible enviar el compilador a un bucle infinito al usar esta extensión.

La solución común a esto es añadir un 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) 

Ahora las limitaciones son más pequeños que la cabeza ejemplo, a medida que se desnudan la newtype. No se requiere extensión.

Answer 2

hammar ya proporcionó una solución; Me gustaría señalar otro problema con este ejemplo. Lo que quiere expresar es "Siempre que un tipo sea una instancia de Eq y EuclideanDomain, use esta regla para crear una instancia para Ord". Pero esto es inexpresable en Haskell. La línea

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

en realidad significa "utilizar esta regla para hacer una instancia Ord para cualquier tipo. Es un error si las instancias de EuclideanDomain y Eq no son de alcance". Eso no es bueno, porque esta regla se superpondrá con cualquier otra instancia de Ord.

Básicamente en cualquier momento que desee escribir una instancia Class typevar, necesitará un nuevo tipo.