Reposting to libraries, since I was advised that this would be the correct place, and not haskell-prime, as I assumed because it would change behaviour specified in the language report. The proposal has been made earlier and received widespread support, but it was never finished. This time, on the haskell-prime list, http://www.haskell.org/pipermail/haskell-prime/2011-May/003403.html, Jaques Carette and Cale Gibbard already recorded their support. Discussion period: two weeks, until 11. June 2011. An old and reopened ticket is at: http://hackage.haskell.org/trac/ghc/ticket/3304 The Proposal: I would like to propose the elimination of the special error case gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined" to replace it with gcd 0 0 = 0 (which would be an automatic consequence of removing the above line). Rationale: 1. It makes gcd a total function. 2. It makes gcd associative. 3. It makes folding gcd over a list safe. 4. It conforms to common mathematical practice: In a commutative ring, a greatest common divisor of two elements a, b is a common divisor g of a and b such that every common divisor d of a and b also divides g (if R is a commutative ring, a \in R, d \in R is a divisor of a iff there exists c \in R with a = d*c [leaving out noncommutative rings for simplicity]). Since every ring element divides 0, the above definition entails gcd 0 0 = 0. Further, in a principal ideal ring, the greatest common divisors of two elements a and b are the generators of the ideal (a,b), again that characterisation of greatest common divisors says gcd 0 0 = 0: (0,0) = {0} = (0). Pros: see above. Cons: ? I'm not aware of any, the change shouldn't break existing code, since that would have to check for the special case anyway. There is, however, a difficulty with the documentation. Reading the old threads about the topic (thanks to Judah Jacobson for the links): http://www.haskell.org/pipermail/haskell/2001-December/008560.html http://www.haskell.org/pipermail/haskell-cafe/2009-May/060880.html made me aware that many (probably most) people, upon reading 'greatest' in 'greatest common divisor', think it refers to the natural order of integers and not the divisibility preorder. Of course, historically it did, but since the concept has been expanded to rings which have no natural order, it can't anymore (and even in rings which have a natural order, like Z[sqrt 2], the term 'greatest' can't refer to the natural order if the ring has units > 1). It is not difficult to explain this given enough space, but I don't know yet how to fit it in the limited space a reasonable function documentation provides. Suggestions how to formulate it are welcome. Daniel
On 5/28/11 6:59 AM, Daniel Fischer wrote:
The Proposal:
I would like to propose the elimination of the special error case
gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
to replace it with
gcd 0 0 = 0
(which would be an automatic consequence of removing the above line).
Rationale:
1. It makes gcd a total function. 2. It makes gcd associative. 3. It makes folding gcd over a list safe. 4. It conforms to common mathematical practice:
Just in case I'm not already on the record for this one, +1. The only con I can envision is that, in the general case, the uniqueness of gcd is guaranteed by various properties; whereas every number is a divisor of 0. So, given the uniqueness criterion one could make an argument. However, the common mathematical practice takes gcd 0 0 == 0, and I'm unaware of a compelling reason not to do so. -- Live well, ~wren
On Sunday 29 May 2011 02:15:41, wren ng thornton wrote:
The only con I can envision is that, in the general case, the uniqueness of gcd is guaranteed by various properties; whereas every number is a divisor of 0.
But that makes 0 the largest/greatest element (in the divisibility preorder), whence gcd 0 0 = 0 follows. Actually, that's the only case where the algebraic definition of a gcd results in a unique representative, in all other cases¹, a rule to pick one representative of an equivalence class is needed to make it a (single- valued) function (of type a -> a -> a). In the case of (rational) integers, Z, picking the non-negative element of an equivalence class {x, -x} is a fairly natural choice (but for other purposes, a different choice may be more suitable, e.g. it can be more convenient to pick the representative congruent to 1 (mod 4) for odd primes instead of the positive one).
So, given the uniqueness criterion one could make an argument. However, the common mathematical practice takes gcd 0 0 == 0, and I'm unaware of a compelling reason not to do so.
Indeed all but two options are completely ridiculous. The only defensible options are to leave gcd 0 0 undefined or to have gcd 0 0 = 0. The former has the merit of allowing the term 'greatest' to refer to the normal archimedian order of Z and making the term explicable in concepts familiar to everyone, but that has the serious drawback of restricting the rings in which gcds exist to ordered rings with only two units (1 and -1). [¹] except if the ring has only one unit
+1! On Sat, May 28, 2011 at 6:59 AM, Daniel Fischer < daniel.is.fischer@googlemail.com> wrote:
Reposting to libraries, since I was advised that this would be the correct place, and not haskell-prime, as I assumed because it would change behaviour specified in the language report.
The proposal has been made earlier and received widespread support, but it was never finished. This time, on the haskell-prime list, http://www.haskell.org/pipermail/haskell-prime/2011-May/003403.html, Jaques Carette and Cale Gibbard already recorded their support.
Discussion period: two weeks, until 11. June 2011. An old and reopened ticket is at: http://hackage.haskell.org/trac/ghc/ticket/3304
The Proposal:
I would like to propose the elimination of the special error case
gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
to replace it with
gcd 0 0 = 0
(which would be an automatic consequence of removing the above line).
Rationale:
1. It makes gcd a total function. 2. It makes gcd associative. 3. It makes folding gcd over a list safe. 4. It conforms to common mathematical practice:
In a commutative ring, a greatest common divisor of two elements a, b is a common divisor g of a and b such that every common divisor d of a and b also divides g (if R is a commutative ring, a \in R, d \in R is a divisor of a iff there exists c \in R with a = d*c [leaving out noncommutative rings for simplicity]). Since every ring element divides 0, the above definition entails gcd 0 0 = 0.
Further, in a principal ideal ring, the greatest common divisors of two elements a and b are the generators of the ideal (a,b), again that characterisation of greatest common divisors says gcd 0 0 = 0: (0,0) = {0} = (0).
Pros: see above.
Cons: ? I'm not aware of any, the change shouldn't break existing code, since that would have to check for the special case anyway.
There is, however, a difficulty with the documentation. Reading the old threads about the topic (thanks to Judah Jacobson for the links):
http://www.haskell.org/pipermail/haskell/2001-December/008560.html http://www.haskell.org/pipermail/haskell-cafe/2009-May/060880.html
made me aware that many (probably most) people, upon reading 'greatest' in 'greatest common divisor', think it refers to the natural order of integers and not the divisibility preorder. Of course, historically it did, but since the concept has been expanded to rings which have no natural order, it can't anymore (and even in rings which have a natural order, like Z[sqrt 2], the term 'greatest' can't refer to the natural order if the ring has units > 1).
It is not difficult to explain this given enough space, but I don't know yet how to fit it in the limited space a reasonable function documentation provides.
Suggestions how to formulate it are welcome.
Daniel
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On Saturday 28 May 2011, 12:59:58, I wrote:
Discussion period: two weeks, until 11. June 2011. An old and reopened ticket is at: http://hackage.haskell.org/trac/ghc/ticket/3304
The Proposal:
I would like to propose the elimination of the special error case
gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
to replace it with
gcd 0 0 = 0
(which would be an automatic consequence of removing the above line).
The discussion period is over, nobody objected. The proposal was supported by Jacques Carette, Cale Gibbard, Sebastian Fischer, Wren Ng Thornton, Ross Paterson, Edward Kmett, Yitzchak Gale (and various others on previous occasions). There was some discussion about the formulation of the documentation, I hope the variant in the patch (based on Ross Paterson's suggestion) is sufficiently clear.
participants (4)
-
Daniel Fischer -
Edward Kmett -
wren ng thornton -
Yitzchak Gale