33

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?

Xodarap
  • 11,581
  • 11
  • 56
  • 94

2 Answers2

39

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.

John L
  • 27,937
  • 4
  • 73
  • 88
32

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.

hammar
  • 138,522
  • 17
  • 304
  • 385
  • 5
    What does it mean for the constraints to be smaller? Surely there are fewer `EuclideanDomain a`s then there are `a`s? – Xodarap Aug 26 '11 at 01:28
  • 8
    @Xodarap: Smaller as in "wrapped in fewer type constructors", not as in "fewer values of this type". – hammar Aug 26 '11 at 01:42
  • I see. When I try what you put here and then `f :: EuclideanDomain a => a -> Ordering`, `f x = compare x x` it doesn't compile. What am I missing? – Xodarap Aug 26 '11 at 01:52
  • @Xodarap: Without extensions this rule is quite trivial. The instance head must be of the form `T a1 .. an`, and the constraints may only apply to the `as`. However, with `FlexibleContexts` you can have code like `instance C1 (Foo a) => C2 (Bar (Foo a))`, and here `Foo a` in the context is smaller than `Bar (Foo a)` in the instance head. – hammar Aug 26 '11 at 01:54
  • @Xodarap: You have to work with the `newtype`. So it would be `f :: (EuclideanDomain a, Eq a) => ByNorm a -> Ordering`, or in this case just the unrestricted `f :: Ord a => a -> Ordering`. – hammar Aug 26 '11 at 01:58