Opened 11 years ago

Closed 9 years ago

# define gcd 0 0 = 0

Reported by: Owned by: stevec normal 7.2.1 libraries/base 7.1 libraries@…, gale@…, asr, daniel.is.fischer@…, hvr, ekmett Unknown/Multiple Unknown/Multiple None/Unknown

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

\$ 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. ]

### comment:1 Changed 11 years ago by guest

There was a discussion about that issue years ago:

### comment:2 Changed 11 years ago by igloo

difficulty: → Unknown → Not GHC

### comment:3 follow-up:  4 Changed 10 years ago by igloo

Resolution: → wontfix new → closed → None/Unknown

Looks like an abandoned proposal

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

Cc: gale@… added wontfix closed → new

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:

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 simonmar

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

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.

### Changed 9 years ago by daniel.is.fischer

Patch for GHC.Real

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

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 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?

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

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:

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

### comment:15 Changed 9 years ago by igloo

Resolution: → fixed 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 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 follow-up:  18 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

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 follow-up:  21 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 ; follow-up:  23 Changed 9 years ago by ross

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.