Opened 10 years ago

Closed 10 years ago

Last modified 8 years ago

#1517 closed bug (wontfix)

Ratio Int is not well ordered

Reported by: dbenbenn@… Owned by:
Priority: normal Milestone:
Component: libraries/base Version: 6.6.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


Ratio Int is declared to be in class Ord, which means (according to that < should be a total ordering. Yet consider the following interactive session in GHCI (on a 32 bit computer!):

Prelude> :m + Ratio
Prelude Ratio> let a = 1 % (2 :: Int)
Prelude Ratio> let b = 883177231 % (662415279 :: Int)
Prelude Ratio> let c = 1616076535 % (430549561 :: Int)
Prelude Ratio> a < b && b < c
Prelude Ratio> a < c

The problem is that overflow occurs in Real.lhs (from the GHC source code), in the definition

(x:%y) <  (x':%y')  =  x * y' <  x' * y

That works for unbounded types (such as Integer). But to define a total order on bounded types, a more complicated method is necessary.

See, line 374, for a correct implementation in C++.

Attachments (2)

patch.txt (1.8 KB) - added by dbenbenn@… 10 years ago.
Patch to (mostly) fix the problem
demo.hs (517 bytes) - added by dbenbenn@… 10 years ago.
Examples of overflow bugs

Download all attachments as: .zip

Change History (7)

Changed 10 years ago by dbenbenn@…

Attachment: patch.txt added

Patch to (mostly) fix the problem

Changed 10 years ago by dbenbenn@…

Attachment: demo.hs added

Examples of overflow bugs

comment:1 Changed 10 years ago by dbenbenn@…

difficulty: Easy (1 hr)Moderate (1 day)

I've attached a patch to Real.lhs that mostly fixes the problem. If you apply the patch to GHC 6.6.1 and recompile, then compile demo.hs with the new ghc, it will give the right output. demo.hs will also work right with the new ghci command.

runhaskell and runghc, however, still have the bug. I haven't been able to figure out where their implementation of Ratio is coming from.

comment:2 Changed 10 years ago by igloo

Resolution: wontfix
Status: newclosed

Thanks for the patch, but I see a couple of problems:

  • This would give different behaviour to what the Haskell 98 report specifies
  • This would give unexpected behaviour if the Ord or Num instance for your ratio type don't match those for Integer

I don't have a good solution, I'm afraid. I think we just have to accept that anything involving Int has these sorts of problems.

For example, you could equally say that

x > 0 => y + x > y

should hold, but it doesn't due to Int wrapping.

If you still think that this change should be made then I think that it should go through the library submissions process:

(runhaskell and runghc find ghc on the path, so the reason they were giving the old answers is that they were using your old GHC, not the one you'd fixed. If any change is made, though, then it would also need ).



comment:3 Changed 9 years ago by simonmar

Architecture: MultipleUnknown/Multiple

comment:4 Changed 9 years ago by simonmar

Operating System: MultipleUnknown/Multiple

comment:5 Changed 8 years ago by simonmar

difficulty: Moderate (1 day)Moderate (less than a day)
Note: See TracTickets for help on using tickets.