[ ghc-Bugs-1277810 ] ghc is confused about instances of Ord

Thu Sep 1 04:04:15 EDT 2005

Bugs item #1277810, was opened at 2005-08-31 23:39
Message generated for change (Comment added) made by simonpj
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=108032&aid=1277810&group_id=8032

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Compiler (Type checker)
Group: 6.4
>Status: Closed
>Resolution: Invalid
Priority: 5
Submitted By: Robin Green (greenrd)
Assigned to: Nobody/Anonymous (nobody)
Summary: ghc is confused about instances of Ord

Initial Comment:
When I compile the attached file _without_ -fallow-incoherent-instances 
on ghc 6.4 on Fedora Core Linux, I receive the following errors: 

PartialOrder.hs:19:0: 
    Overlapping instances for PartialOrder a 
      arising from the superclasses of an instance declaration at 
PartialOrder.hs:19:0 
    Matching instances: 
      PartialOrder.hs:11:0: instance (Ord a) => PartialOrder a 
      PartialOrder.hs:19:0: instance PartialOrder (LineList a) 
    (The choice depends on the instantiation of `a' 
     Use -fallow-incoherent-instances to use the first choice above) 
    In the instance declaration for `PartialOrder (LineList a)' 

PartialOrder.hs:20:53: 
    Overlapping instances for PartialOrder a 
      arising from use of `lte' at PartialOrder.hs:20:53-55 
    Matching instances: 
      PartialOrder.hs:11:0: instance (Ord a) => PartialOrder a 
      PartialOrder.hs:19:0: instance PartialOrder (LineList a) 
    (The choice depends on the instantiation of `a' 
     Use -fallow-incoherent-instances to use the first choice above) 
    In the first argument of `zipWith', namely `lte' 
    In the first argument of `and', namely `(zipWith lte c d)' 
    In the definition of `lte': 
        lte (LineList c) (LineList d) = and (zipWith lte c d) 

However, when I compile it _with_ -fallow-incoherent-instances, I 
receive _these_ errors: 

PartialOrder.hs:19:0: 
    No instance for (Ord a) 
      arising from the superclasses of an instance declaration at 
PartialOrder.hs:19:0 
    Probable fix: add (Ord a) to the instance declaration superclass 
context 
    In the instance declaration for `PartialOrder (LineList a)' 

PartialOrder.hs:20:53: 
    Could not deduce (Ord a) 
      from the context (PartialOrder (LineList a), Eq (LineList a)) 
      arising from use of `lte' at PartialOrder.hs:20:53-55 
    Probable fix: add (Ord a) to the class or instance method `lte' 
    In the first argument of `zipWith', namely `lte' 
    In the first argument of `and', namely `(zipWith lte c d)' 
    In the definition of `lte': 
        lte (LineList c) (LineList d) = and (zipWith lte c d) 

So in the _first_ compilation run, ghc is suggesting that an instance of 
Ord a (which I believe is a figment of its imagination) collides; but in the 
_second_ compilation run, it complains that it can't _find_ the instance for 
Ord a. Surely an inconsistency. 

----------------------------------------------------------------------

>Comment By: Simon Peyton Jones (simonpj)
Date: 2005-09-01 08:04

Message:
Logged In: YES 
user_id=50165

Not a figment of its imagination, I'm afraid.

In each case there are two error messages.  Take the second 
message of your first run:

  PartialOrder.hs:20:53: 
  Overlapping instances for PartialOrder a 
  arising from use of `lte' at PartialOrder.hs:20:53-55 
  Matching instances: 
  PartialOrder.hs:11:0: instance (Ord a) => PartialOrder a 
  PartialOrder.hs:19:0: instance PartialOrder (LineList a) 
  (The choice depends on the instantiation of `a' 
  Use -fallow-incoherent-instances to use the first choice 
above) 
  In the first argument of `zipWith', namely `lte' 
  In the first argument of `and', namely `(zipWith lte c d)' 
  In the definition of `lte': 
  lte (LineList c) (LineList d) = and (zipWith lte c d) 

This is quite right.  The call of "lte" needs (PartialOrder a).  
But there are two ways
to resolve this constraint, depending on how 'a' is 
instantiated.  To see the difference,
suppose you were calling lte on arguments of type
	(LineList (LineList Int))  

The second message of the second run is similar.  -fallow-
incoherent-instances says 
"don't worry about how 'a' is instantiated, just go for it".  So 
GHC resolves the
(PartialOrder a) constraint using the instance decl on line 11, 
and now it needs
(Ord a).  But there's no Ord a available, so the program is 
rightly rejected.

The first error message of each run is more perplexing, and 
relates to
a mis-feature of Haskell.  When you write 
	data (PartialOrder a) => LineList a = LineList [a]
the (PartialOrder a) constraint is unleashed not only when 
you *build* a
LineList, but also when you *pattern match* on one.  So the 
derived Eq instance
for LineList looks like this:
	instance (PartialOrder a) => Eq (LineList a) 
where ...

Now you know that you can probably work out where the first 
error message
comes from.

The whole semantics of a "context on a data type 
declaration" is a mis-feature
of Haskell.  In GHC's source code it's called the "stupid 
theta".  My advice is
never to use it.  You'll be quite ok with
	data LineList a = LineList [a] deriving( Eq, Show )

If you want overlapping instances, incoherent instances, then 
indeed things
get complicated.  That's why the flags have long and 
forbidding names!
-}

----------------------------------------------------------------------

Comment By: Robin Green (greenrd)
Date: 2005-09-01 00:23

Message:
Logged In: YES 
user_id=2202

The general problem here seems to be that ghc is not being very smart about 
making trivial instance deductions that may be very obvious to the 
programmer. Here is another example:    

mkLineBunch :: (Ord a) => [[a]] -> LineBunch a    
mkLineBunch = (uncurry LineBunch) . ((uncurry withBoth) ((map `ofBoth`    
minimum) maximum)) . transpose    

ghc complains here about instance collisions. But if the _logically_ equivalent   
type signature is substituted:   

mkLineBunch :: (Ord a, PartialOrder a) => [[a]] -> LineBunch a   

the file suddenly compiles successfully! So the first error message was bogus,   
and apparently arose from the compiler being unable to deduce that Ord a   
implies PartialOrder a, even though it had been _told_ that Ord a =>  
PartialOrder a above.  

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=108032&aid=1277810&group_id=8032