#3304 closed proposal (fixed)
define gcd 0 0 = 0
Reported by: | stevec | Owned by: | |
---|---|---|---|
Priority: | normal | Milestone: | 7.2.1 |
Component: | libraries/base | Version: | 7.1 |
Keywords: | Cc: | libraries@…, gale@…, asr, daniel.is.fischer@…, hvr, ekmett | |
Operating System: | Unknown/Multiple | Architecture: | Unknown/Multiple |
Type of failure: | None/Unknown | Test Case: | |
Blocked By: | Blocking: | ||
Related Tickets: | Differential Rev(s): | ||
Wiki Page: |
Description
Please make any comments on the libraries list by Tuesday 15th September 2009.
A suggestion to change 'gcd 0 0' from
gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
to
gcd 0 0 = 0
The proposal has been discussed on haskell-cafe@… http://www.haskell.org/pipermail/haskell-cafe/2009-May/060788.html and there was a lot of support for the suggested change.
Current code: libraries/base/GHC/Real.lhs
-- | @'gcd' x y@ is the greatest (positive) integer that divides both @x@ -- and @y@; for example @'gcd' (-3) 6@ = @3@, @'gcd' (-3) (-6)@ = @3@, -- @'gcd' 0 4@ = @4@. @'gcd' 0 0@ raises a runtime error. gcd :: (Integral a) => a -> a -> a gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined" gcd x y = gcd' (abs x) (abs y) where gcd' a 0 = a gcd' a b = gcd' b (a `rem` b)
Suggested code:
-- | @'gcd' x y@ is the greatest (positive) integer that divides both @x@ -- and @y@; for example @'gcd' (-3) 6@ = @3@, @'gcd' (-3) (-6)@ = @3@, -- @'gcd' 0 4@ = @4@. @'gcd' 0 0@ is defined to be 0. gcd :: (Integral a) => a -> a -> a gcd x y = gcd' (abs x) (abs y) where gcd' a 0 = a gcd' a b = gcd' b (a `rem` b)
[Note: I tried following the instructions at http://www.haskell.org/haskellwiki/Library_submissions to create a darcs patch. I successfully downloaded a copy of HEAD, but was unable to create a patch:
$ darcs record libraries/base/GHC/Real.lhs Recording changes in "libraries/base/GHC/Real.lhs":
No changes in selected files or directories!
I would claim that the instructions are insufficient for a darcs beginner. ]
Attachments (8)
Change History (32)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
difficulty: | → Unknown |
---|---|
Milestone: | → Not GHC |
comment:3 follow-up: 4 Changed 10 years ago by
Resolution: | → wontfix |
---|---|
Status: | new → closed |
Type of failure: | → None/Unknown |
Looks like an abandoned proposal
comment:4 Changed 9 years ago by
Cc: | gale@… added |
---|---|
Resolution: | wontfix |
Status: | closed → new |
Replying to igloo:
Looks like an abandoned proposal
No, it just keeps getting mired in Library Proposal red tape.
It came up yet again, this time proposed by Daniel Fischer with comprehensive justification:
http://www.haskell.org/pipermail/haskell-prime/2011-May/003403.html
Every time, it gets universal enthusiastic support, then dies on procedure. Could you please just apply it? CC the haskell-prime list so that they'll apply it there, too.
Thanks!
comment:5 follow-up: 6 Changed 9 years ago by
Milestone: | Not GHC → 7.2.1 |
---|
So we need to change gcd
in GHC.Real
, but also reinstate the old behaviour for the haskell98
and haskell2010
packages, correct?
comment:6 Changed 9 years ago by
Replying to simonmar:
So we need to change
gcd
inGHC.Real
, but also reinstate the old behaviour for thehaskell98
andhaskell2010
packages, correct?
I suppose that would be the squeaky-clean way of doing
things, especially since the documentation explicitly
mentions the old behavior of calling error
.
But most people view this as a bug fix. It seems highly unlikely that anyone would really want the old behavior for anything.
Personally, I would be happy either way, as long as it finally gets fixed.
comment:7 Changed 9 years ago by
Cc: | andres.sicard.ramirez@… added |
---|
comment:8 Changed 9 years ago by
Cc: | daniel.is.fischer@… added |
---|
Changed 9 years ago by
Attachment: | gcd_0_0_haskell2010.patch added |
---|
Patch for the haskell2010 library
comment:9 Changed 9 years ago by
Status: | new → patch |
---|
The patches passed a validate-build, so they are warning-clean.
It would be nice to have them in 7.2 because that would enhance the chances to fix the issue in the next standard.
comment:10 follow-up: 11 Changed 9 years ago by
How did you generate those patches? They aren't in the right format for feeding into git am
. Could you try git format-patch
please?
Changed 9 years ago by
Attachment: | 0001-Adjust-behaviour-of-gcd.patch added |
---|
comment:11 Changed 9 years ago by
Replying to simonmar:
How did you generate those patches? They aren't in the right format for feeding into
git am
. Could you trygit format-patch
please?
I used git log -p
, since git diff -p
didn't include the commit message, didn't know about format-patch (with git, I'm happy if I don't need to reset --hard
to get a working repo again). Sorry.
Re-reading the old threads, the comment needs to explain what greatest
means in connection to gcd (and divisibility in general), haven't thought about how to formulate that yet.
comment:12 Changed 9 years ago by
The continuation of the current discussion thread has moved from the haskell-prime list to the libraries list:
http://www.haskell.org/pipermail/libraries/2011-May/016411.html
Changed 9 years ago by
Attachment: | 0001-New-gcd-documentation.patch added |
---|
suggested new haddock for gcd
Changed 9 years ago by
Attachment: | 0001-Change-gcd-to-reduce-occurrences-of-negative-results.patch added |
---|
abs the result of gcd to avoid negative results where possible
comment:13 Changed 9 years ago by
Version: | 6.10.3 → 7.1 |
---|
The last patch isn't directly related to the proposal, but since it came up in the thread, I'm attaching it here nevertheless. It changes the behaviour to match the docs more closely. With signed bounded integer types, many results of gcd
are negative if one of the arguments is minBound
, calling a final abs
eliminates those except if the result is minBound
.
comment:14 Changed 9 years ago by
Discussion period over. No objections were raised. Proposal supported by Jacques Carette, Cale Gibbard, Sebastian Fischer, Wren Ng Thornton, Ross Paterson, Edward Kmett, Yitzchak Gale.
Please review and apply.
comment:15 Changed 9 years ago by
Resolution: | → fixed |
---|---|
Status: | patch → closed |
Applied all but the last one. I'm not sure about it; should we throw an exception in the minBound case, like we do for dividing by -1?
comment:16 Changed 9 years ago by
Thanks.
The only feasible ways to throw an exception I see are
case {- abs $ -} gcd' (abs x) (abs y) of g | g < 0 -> overflowError | otherwise -> g
or
let x' = abs x y' = abs y in if x' < 0 || y' < 0 then overflowError else gcd' x' y'
In the former case, the abs
on the result would be much better, or you'd get an overflowError half the time when one argument is minBound for signed bounded types, which would be hard to predict and understand. In the latter case, you'd get consistent and predictable exceptions, but unnecessarily many, in my opinion.
I would prefer to not throw an exception, however, because often you can carry on perfectly well with a negative result.
comment:17 follow-up: 18 Changed 9 years ago by
It could be done by having abs minBound throw an exception (which seems justifiable).
comment:18 Changed 9 years ago by
Replying to ross:
It could be done by having abs minBound throw an exception (which seems justifiable).
That sounds sensible, and would handle the result of
minBound `gcd` minBound :: Int
correctly, but we wouldn't want to get an exception from taking abs
of the arguments in
minBound `gcd` (minBound `div` 2) :: Int
comment:19 Changed 9 years ago by
But we don't need to take abs of the arguments, if we're doing an abs on the result of gcd'.
comment:20 follow-up: 21 Changed 9 years ago by
I thought so, too, for a while, but when I tried that, I ran into gcd minBound (-1), which throws the overflowError, so unfortunately we have to call abs on the arguments (or go via Integer for all types).
comment:21 follow-up: 23 Changed 9 years ago by
Replying to daniel.is.fischer:
I thought so, too, for a while, but when I tried that, I ran into gcd minBound (-1), which throws the overflowError
because rem minBound (-1)::Int throws overflowError, but surely that's a bug: quot minBound (-1)::Int should overflow, but rem minBound (-1)::Int should be 0.
comment:22 Changed 9 years ago by
comment:23 Changed 9 years ago by
Replying to ross:
Replying to daniel.is.fischer:
I thought so, too, for a while, but when I tried that, I ran into gcd minBound (-1), which throws the overflowError
because rem minBound (-1)::Int throws overflowError, but surely that's a bug: quot minBound (-1)::Int should overflow, but rem minBound (-1)::Int should be 0.
Good point. Fixed in changeset:9b02e90c860f41c6431e6a0015ea4f02ec770ced.
comment:24 Changed 5 years ago by
Cc: | asr hvr ekmett added; andres.sicard.ramirez@… removed |
---|
There was a discussion about that issue years ago: