Opened 7 years ago

Closed 7 years ago

Last modified 4 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: Difficulty: Moderate (less than a day)
Test Case: Blocked By:
Blocking: Related Tickets:

Description

Ratio Int is declared to be in class Ord, which means (according to http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Ord.html#t%3AOrd) 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
True
Prelude Ratio> a < c
False

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 http://boost.cvs.sourceforge.net/boost/boost/boost/rational.hpp?revision=1.21&view=markup, line 374, for a correct implementation in C++.

Attachments (2)

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

Download all attachments as: .zip

Change History (7)

Changed 7 years ago by dbenbenn@…

Patch to (mostly) fix the problem

Changed 7 years ago by dbenbenn@…

Examples of overflow bugs

comment:1 Changed 7 years ago by dbenbenn@…

  • Difficulty changed from Easy (1 hr) to 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 7 years ago by igloo

  • Resolution set to wontfix
  • Status changed from new to closed

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: http://www.haskell.org/haskellwiki/Library_submissions

(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 ).

Thanks

Ian

comment:3 Changed 6 years ago by simonmar

  • Architecture changed from Multiple to Unknown/Multiple

comment:4 Changed 6 years ago by simonmar

  • Operating System changed from Multiple to Unknown/Multiple

comment:5 Changed 4 years ago by simonmar

  • Difficulty changed from Moderate (1 day) to Moderate (less than a day)
Note: See TracTickets for help on using tickets.