Opened 11 years ago

Closed 9 years ago

Last modified 5 years ago

#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)

gcd_0_0_commit.patch (1.8 KB) - added by daniel.is.fischer 9 years ago.
Patch for GHC.Real
gcd_0_0_haskell98.patch (1.1 KB) - added by daniel.is.fischer 9 years ago.
Patch for the haskell98 library
gcd_0_0_haskell2010.patch (1.1 KB) - added by daniel.is.fischer 9 years ago.
Patch for the haskell2010 library
0001-Adjust-behaviour-of-gcd.patch (1.9 KB) - added by daniel.is.fischer 9 years ago.
0001-Add-old-behaviour-of-gcd-h98.patch (1.2 KB) - added by daniel.is.fischer 9 years ago.
haskell98
0001-Add-old-behaviour-of-gcd-h2010.patch (1.2 KB) - added by daniel.is.fischer 9 years ago.
haskell2010
0001-New-gcd-documentation.patch (1.6 KB) - added by daniel.is.fischer 9 years ago.
suggested new haddock for gcd
0001-Change-gcd-to-reduce-occurrences-of-negative-results.patch (905 bytes) - added by daniel.is.fischer 9 years ago.
abs the result of gcd to avoid negative results where possible

Download all attachments as: .zip

Change History (32)

comment:1 Changed 11 years ago by guest

There was a discussion about that issue years ago:

http://www.haskell.org/pipermail/haskell/2001-December/008609.html

comment:2 Changed 11 years ago by igloo

difficulty: Unknown
Milestone: Not GHC

comment:3 Changed 10 years ago by igloo

Resolution: wontfix
Status: newclosed
Type of failure: None/Unknown

Looks like an abandoned proposal

comment:4 in reply to:  3 Changed 9 years ago by YitzGale

Cc: gale@… added
Resolution: wontfix
Status: closednew

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 Changed 9 years ago by simonmar

Milestone: Not GHC7.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 in reply to:  5 Changed 9 years ago by YitzGale

Replying to simonmar:

So we need to change gcd in GHC.Real, but also reinstate the old behaviour for the haskell98 and haskell2010 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 asr

Cc: andres.sicard.ramirez@… added

comment:8 Changed 9 years ago by daniel.is.fischer

Cc: daniel.is.fischer@… added

Changed 9 years ago by daniel.is.fischer

Attachment: gcd_0_0_commit.patch added

Patch for GHC.Real

Changed 9 years ago by daniel.is.fischer

Attachment: gcd_0_0_haskell98.patch added

Patch for the haskell98 library

Changed 9 years ago by daniel.is.fischer

Attachment: gcd_0_0_haskell2010.patch added

Patch for the haskell2010 library

comment:9 Changed 9 years ago by daniel.is.fischer

Status: newpatch

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 Changed 9 years ago by simonmar

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 daniel.is.fischer

Changed 9 years ago by daniel.is.fischer

haskell98

Changed 9 years ago by daniel.is.fischer

haskell2010

comment:11 in reply to:  10 Changed 9 years ago by daniel.is.fischer

Replying to simonmar:

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?

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 YitzGale

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 daniel.is.fischer

suggested new haddock for gcd

Changed 9 years ago by daniel.is.fischer

abs the result of gcd to avoid negative results where possible

comment:13 Changed 9 years ago by daniel.is.fischer

Version: 6.10.37.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 daniel.is.fischer

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 igloo

Resolution: fixed
Status: patchclosed

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 daniel.is.fischer

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 Changed 9 years ago by ross

It could be done by having abs minBound throw an exception (which seems justifiable).

comment:18 in reply to:  17 Changed 9 years ago by igloo

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 ross

But we don't need to take abs of the arguments, if we're doing an abs on the result of gcd'.

comment:20 Changed 9 years ago by 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, so unfortunately we have to call abs on the arguments (or go via Integer for all types).

comment:21 in reply to:  20 ; Changed 9 years ago by 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.

comment:22 Changed 9 years ago by daniel.is.fischer

I'd prefer wrapping to overflow for all of div, mod, quot, rem, but see #1042, #2166, #3065 for why things are as they are. If #3065 is resolved by changing the behaviour to wrapping,

gcd x y = abs (gcd' x y)

would be my choice.

comment:23 in reply to:  21 Changed 9 years ago by igloo

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 asr

Cc: asr hvr ekmett added; andres.sicard.ramirez@… removed
Note: See TracTickets for help on using tickets.