GHC: Ticket #1517: Ratio Int is not well ordered
http://ghc.haskell.org/trac/ghc/ticket/1517
<p>
Ratio Int is declared to be in class Ord, which means (according to <a class="ext-link" href="http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Ord.html#t%3AOrd"><span class="icon"></span>http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Ord.html#t%3AOrd</a>) that < should be a total ordering. Yet consider the following interactive session in GHCI (on a 32 bit computer!):
</p>
<pre class="wiki">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
</pre><p>
The problem is that overflow occurs in Real.lhs (from the GHC source code), in the definition
</p>
<pre class="wiki">(x:%y) < (x':%y') = x * y' < x' * y
</pre><p>
That works for unbounded types (such as Integer). But to define a total order on bounded types, a more complicated method is necessary.
</p>
<p>
See <a class="ext-link" href="http://boost.cvs.sourceforge.net/boost/boost/boost/rational.hpp?revision=1.21&view=markup"><span class="icon"></span>http://boost.cvs.sourceforge.net/boost/boost/boost/rational.hpp?revision=1.21&view=markup</a>, line 374, for a correct implementation in C++.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/1517
Trac 1.0.1dbenbenn@…Sat, 21 Jul 2007 18:20:50 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/1517
http://ghc.haskell.org/trac/ghc/ticket/1517
<ul>
<li><strong>attachment</strong>
set to <em>patch.txt</em>
</li>
</ul>
<p>
Patch to (mostly) fix the problem
</p>
Ticketdbenbenn@…Sat, 21 Jul 2007 18:22:56 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/1517
http://ghc.haskell.org/trac/ghc/ticket/1517
<ul>
<li><strong>attachment</strong>
set to <em>demo.hs</em>
</li>
</ul>
<p>
Examples of overflow bugs
</p>
Ticketdbenbenn@…Sat, 21 Jul 2007 18:27:14 GMTdifficulty changed
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:1
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:1
<ul>
<li><strong>difficulty</strong>
changed from <em>Easy (1 hr)</em> to <em>Moderate (1 day)</em>
</li>
</ul>
<p>
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.
</p>
<p>
runhaskell and runghc, however, still have the bug. I haven't been able to figure out where their implementation of Ratio is coming from.
</p>
TicketiglooSat, 21 Jul 2007 19:18:56 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:2
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>wontfix</em>
</li>
</ul>
<p>
Thanks for the patch, but I see a couple of problems:
</p>
<ul><li>This would give different behaviour to what the Haskell 98 report specifies
</li><li>This would give unexpected behaviour if the Ord or Num instance for your ratio type don't match those for Integer
</li></ul><p>
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.
</p>
<p>
For example, you could equally say that
</p>
<pre class="wiki">x > 0 => y + x > y
</pre><p>
should hold, but it doesn't due to Int wrapping.
</p>
<p>
If you still think that this change should be made then I think that it should go through the library submissions process: <a class="ext-link" href="http://www.haskell.org/haskellwiki/Library_submissions"><span class="icon"></span>http://www.haskell.org/haskellwiki/Library_submissions</a>
</p>
<p>
(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 ).
</p>
<p>
Thanks
</p>
<p>
Ian
</p>
TicketsimonmarTue, 30 Sep 2008 15:45:11 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:3
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:3
<ul>
<li><strong>architecture</strong>
changed from <em>Multiple</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:54:48 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:4
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:4
<ul>
<li><strong>os</strong>
changed from <em>Multiple</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarMon, 16 Nov 2009 13:11:50 GMTdifficulty changed
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:5
http://ghc.haskell.org/trac/ghc/ticket/1517#comment:5
<ul>
<li><strong>difficulty</strong>
changed from <em>Moderate (1 day)</em> to <em>Moderate (less than a day)</em>
</li>
</ul>
Ticket