スタック・オーバーフローに参加する
680万人以上のプログラマーが集まるスタック・オーバーフローに参加しませんか？
簡単な登録後、すぐにご利用いただけます。
登録
up vote 22 down vote favorite
4

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?

share|improve this question
up vote 20 down vote

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.

share|improve this answer
1  
What does it mean for the constraints to be smaller? Surely there are fewer EuclideanDomain as then there are as? – Xodarap Aug 26 '11 at 1:28
4  
@Xodarap: Smaller as in "wrapped in fewer type constructors", not as in "fewer values of this type". – hammar Aug 26 '11 at 1: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 1: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 1: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 1:58
up vote 20 down vote

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.

share|improve this answer
1  
Thanks! This makes it more clear what the issue is. – Xodarap Aug 26 '11 at 12:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.