Proposal: Make gcd total

[Edward Kmett]

+1!

On Sat, May 28, 2011 at 6:59 AM, Daniel Fischer <
daniel.is.fischer at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110529/d43131cb/attachment.htm>