Proposal: Make gcd total

[Daniel Fischer]

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