Hello,
I just noticed that the Haskell Report leaves "gcd 0 0" undefined. Why is
that? I think the gcd of 0 and N should be |N|, the absolute value of N.
Haskell currently does just that, except when N=0: the result of "gcd 0 0"
is undefined instead of 0. I propose to remedy this, but let me first give
some mathematical details.
The definition for 'p divides q' is
p|q == (EX n. n is integer /\ n*p=q)
(All variables are integers by default.) We immediately have p|0 , and a
basic property is
(ALL m. m|a == m|b) == |a|=|b|
where |a| stands for the absolute value of a . Now gcd can be defined by
(a gcd b = c) == c>=0 /\ (ALL m. m|a /\ m|b == m|c)
and it can be proven that this defines a gcd b uniquely for every a and
b . Substituting b=0 gives
a gcd 0 = c
== "definition of gcd"
c>=0 /\ (ALL m. m|a /\ m|0 == m|c)
== "m|0 for every m, see above"
c>=0 /\ (ALL m. m|a == m|c)
== "property of 'divides', see above"
c>=0 /\ |a|=|c|
== "arithmetic"
|a|=c
so that a gcd 0 = |a| for every a .
Actually, the above can be generalized to rational numbers, by assuming all
variables are rational by default. We can even generalize to reals, but
then the existence of a gcd b is not guaranteed anymore; take a=1 and
b=sqrt(2). If it exists, it is still unique, however. In all these cases,
the well-known algorithm used in the Haskell Report can be used to compute
the gcd; if it doesn't exist, this algorithm simply does not terminate.
To make a long story short, I propose to remove the special case "gcd 0 0 =
undefined" from the Haskell Prelude, thereby making "gcd 0 0 = 0". Also, I
propose to make gcd applicable to rational numbers.
Groetjes,
<><
Marnix
--
Marnix Klooster
[EMAIL PROTECTED]
