The Ratio data type suffers from numeric overflow. For example, consider the Ord declaration in the Haskell 98 Report (I'm looking at page 153, section 12.1 of http://haskell.org/definition/haskell98-report.pdf): (x:%y) <= (x':%y') = x * y' <= x' * y It is easy to see that Ratio Int is not well-ordered under this definition, because of overflow. This is a self-contradiction in the Report, since page 84 (section 6.3.2) says that "The Ord class is used for totally ordered datatypes". I think the best way to resolve this contradiction is to avoid overflow. For example, the following definition works: (x:%y) <= (x':%y') = (toInteger x) * (toInteger y') <= (toInteger x') * (toInteger y) I submitted a complete patch at http://hackage.haskell.org/trac/ghc/ticket/1517, but that was apparently the wrong place, since the bug was closed as wontfix. Is there a chance of getting this contradiction resolved? I'll be happy to provide unit tests for the change if that will help get it applied.
I am going to take a guess and say that the library policy is that (Num Integer) and (Ratio Integer) are known to follow the axioms, but anyone who uses (Num Int) and (Ratio Int) did so to get the size and performance and does not want to cast to Integer. Just as someone who uses (Word8) really wants to conserve space, much as the Array of Bool is usually implemented as bitpacked in memory. David Benbennick wrote:
The Ratio data type suffers from numeric overflow. For example, consider the Ord declaration in the Haskell 98 Report (I'm looking at page 153, section 12.1 of http://haskell.org/definition/haskell98-report.pdf):
(x:%y) <= (x':%y') = x * y' <= x' * y
It is easy to see that Ratio Int is not well-ordered under this definition, because of overflow. This is a self-contradiction in the Report, since page 84 (section 6.3.2) says that "The Ord class is used for totally ordered datatypes".
I think the best way to resolve this contradiction is to avoid overflow. For example, the following definition works:
(x:%y) <= (x':%y') = (toInteger x) * (toInteger y') <= (toInteger x') * (toInteger y)
I submitted a complete patch at http://hackage.haskell.org/trac/ghc/ticket/1517, but that was apparently the wrong place, since the bug was closed as wontfix.
Is there a chance of getting this contradiction resolved? I'll be happy to provide unit tests for the change if that will help get it applied. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On 7/22/07, haskell@list.mightyreason.com
I am going to take a guess and say that the library policy is that (Num Integer) and (Ratio Integer) are known to follow the axioms, but anyone who uses (Num Int) and (Ratio Int) did so to get the size and performance and does not want to cast to Integer.
The current implementation of < for Ratio Int is no better than a coin flip. That is, if you take two elements of Ratio Int at random and compare them with <, the answer will be right 50% of the time, and wrong 50% of the time. I would assume that if someone is comparing two elements of Ratio Int with <, they're doing so because they want the right answer. If they don't care what answer they get, they can just assume True and be even more efficient. Also, I don't think it's generally well known that the overflow problems are as bad as they are. For example, the documentation at http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Ratio.html doesn't include any warnings that Ratio Int doesn't obey the documented behavior of Ord.
On Sat, Jul 21, 2007 at 04:03:38PM +0000, David Benbennick wrote:
I submitted a complete patch at http://hackage.haskell.org/trac/ghc/ticket/1517, but that was apparently the wrong place, since the bug was closed as wontfix.
For those who haven't read the bug log, here is the closure message: 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 Thanks Ian
On 7/22/07, Ian Lynagh
* This would give different behaviour to what the Haskell 98 report specifies
As I said earlier, the Report is self-contradictory on this issue, so it's not entirely well-defined what the 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 understand this comment. Could you clarify?
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.
Well, the question is what properties can you achieve, and what properties are not achievable? You're right that "x > 0 => y + x > y" is not achievable for Ratio Int, but the documentation doesn't assert that property anywhere, and no one would reasonably expect that property, since it isn't possible. On the other hand, it IS possible to achieve the property that "a < b && b < c => a < c". And since the documentation says that Ratio Int satisfies this property, it is entirely reasonable to expect that it actually does.
participants (3)
-
David Benbennick -
haskell＠list.mightyreason.com -
Ian Lynagh