Proposal: Make gcd total
Daniel Fischer
daniel.is.fischer at googlemail.com
Sat May 28 12:59:58 CEST 2011
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
More information about the Libraries
mailing list