Thanks for all the replies, it looks like there is a lot of support for having gcd 0 0 = 0. I've since discovered that there was a similar discussion in 2001, where the majority supported gcd 0 0 = 0, but the suggested change was never implemented. http://www.haskell.org/pipermail/haskell/2001-December/008560.html On Sat, 2009-05-02 at 13:17 +0200, Martijn van Steenbergen wrote:

Hi Steve,

Steve wrote:

...

Why is gcd 0 0 undefined?

That's a good question. Can you submit an official proposal?

http://www.haskell.org/haskellwiki/Library_submissions

Thanks,

Martijn.

OK, I'll work my way through proposal steps. Steve

Am Sonntag 03 Mai 2009 00:17:22 schrieb Achim Schneider:

Steve wrote:

...

"It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below."

Ouch. Speak of mathematicians annoying programmers by claiming that 0 isn't divisible by any of [1..],

Beg pardon? 0 is divisible by all of them. And while we're talking about rings, 0 is also divisible by 0.

and further implying that 0 is bigger than all of those,

'Tis, in the divisibility preorder :)

not to mention justifying all that with long words.

Sorry for the long words, but having gcd 0 0 == lcm 0 0 == 0 is the sensible thing and having it differently in Haskell is a bad mistake (IMO).

Damn them buggers.

Having gcd(0,0) = 0 doesn't mean that 0 is not divisible by any other natural number. On the contrary, any natural trivially divides 0 since n*0 = 0. Perhaps the disagreement is over what is meant by "greatest". The "greatest" in gcd is not w.r.t. the canonical ordering on the naturals; rather w.r.t. the partial order given by the divides relation. Similarly for the "least" in lcm. Suppose gcd(0,0) = a. Then a|0, and if b|0 then b|a. (That's what it means to be the gcd.) So what is a? Since every natural number divides zero, a must be divisible by every natural number. The only natural number with this property is 0, which can be proved using the essential uniqueness of prime factorizations and infinitude of primes. So having gcd(0,0) = 0 isn't just useful, it's the correct thing to do. I hope that didn't use too many long words. :) -Nathan Bloomfield Grad Assistant, University of Arkansas, Fayetteville On Sat, May 2, 2009 at 5:17 PM, Achim Schneider wrote:

Steve wrote:

...

"It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below."

Ouch. Speak of mathematicians annoying programmers by claiming that 0 isn't divisible by any of [1..], and further implying that 0 is bigger than all of those, not to mention justifying all that with long words.

Damn them buggers.

-- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

This, to defend myself, was not how it was explained in high school.

No worries. I didn't realize this myself until college; most nonspecialist teachers just don't know any better. Nor did, it appears, the original authors of the Haskell Prelude. :) BTW, this definition of gcd makes it possible to consider gcds in rings that otherwise have no natural order- such as rings of polynomials in several variables, group rings, et cetera. Nathan Bloomfield On Sun, May 3, 2009 at 11:16 AM, Achim Schneider wrote:

Nathan Bloomfield wrote:

...

The "greatest" in gcd is not w.r.t. the canonical ordering on the naturals; rather w.r.t. the partial order given by the divides relation.

This, to defend myself, was not how it was explained in high school.

-- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Am Sonntag 03 Mai 2009 18:16:38 schrieb Achim Schneider:

Nathan Bloomfield wrote:

...

The "greatest" in gcd is not w.r.t. the canonical ordering on the naturals; rather w.r.t. the partial order given by the divides relation.

Nitpick: it's not a partial order, but a preorder (2 | (-2), (-2) | 2, 2 /= (-2)).

This, to defend myself, was not how it was explained in high school.

Understandably. One wouldn't want to confuse the average pupil with too abstract concepts like arbitrary rings or preorders. Unfortunately that leads to teaching concepts of primes, greatest common divisors and least common multiples which don't agree with the modern mathematical concepts :-(