CODEWITHSUNDEEP
haskell
Xodarap
Xodarap

Reputation: 11849

Haskell Constraint is no smaller than the instance head

Some rings can be equipped with a norm function:

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

With this function, the ring can be ordered in the obvious way:

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

But I'm not sure how to indicate this. I tried to do

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

but this gives me some warnings, and when I enable the relevant compiler flags it tells me "Constraint is no smaller than the instance head" - if I enable UndecidableInstances everything goes to hell.

Is there a way to do what I want?

Upvotes: 35

Views: 6278

Answers (2)

John L
John L

Reputation: 28097

hammar's already provided a solution; I'd like to point out another problem with this example. What you want to express is "Whenever a type is an instance of Eq and EuclideanDomain, use this rule to make an instance for Ord." But this is inexpressible in Haskell. The line

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

actually means, "Use this rule to make an Ord instance for any type. It's an error if instances of EuclideanDomain and Eq aren't in scope". That's not good, because this rule will overlap with every other Ord instance.

Basically any time you want to write an instance Class typevar, you're going to need a newtype.

Upvotes: 39

hammar
hammar

Reputation: 139900

In order to avoid infinite loops, the compiler normally requires that the constraints of an instance are "smaller" than the instance itself, so that the algorithm will terminate. Your instance does not make a any smaller in the constraints, so that's what the compiler is complaining about.

The UndecidableInstances extension lifts this restriction, leaving it up to you to prove that it will terminate. It's thus possible to send the compiler into an infinite loop when using this extension.

The common solution to this is to add a 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)

Now the constraints are smaller than the instance head, as they strip off the newtype. No extension required.

Upvotes: 32

Related Questions