[Haskell-beginners] gcd

[Daniel Fischer]

Am Freitag 01 Mai 2009 22:28:12 schrieb Daniel Carrera:
> I'm just another Haskell beginner, but what Steve says makes sense.

Yes, it's something I've often been annoyed by.
It's a wart (rather an error) in the Haskell report 
http://haskell.org/onlinereport/basic.html#sect6.4.2
where it's specified that gcd 0 0 shall raise a runtime error. I hope that gets fixed in 
the next standard.

> Perhaps something like this:
>
> gcd a b | b == 0    = a
>
>          | b < 0     = gcd (-b) a
>          | otherwise = gcd b (a `rem` b)
>
> Daniel.

No, that would check for negative numbers in each iteration. Just remove the line

gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"

and everything's fine.
>
> Steve wrote:
> > I had a look at the gcd definition in GHC 6.10.1
> > ghc-6.10.1/libraries/base/GHC/Real.lhs
> >
> > -- | @'gcd' x y@ is the greatest (positive) integer that divides both
> > @x@
> > -- and @y@; for example @'gcd' (-3) 6@ = @3@, @'gcd' (-3) (-6)@ = @3@,
> > -- @'gcd' 0 4@ = @4 at .  @'gcd' 0 0@ raises a runtime error.
> > gcd             :: (Integral a) => a -> a -> a
> > gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"
> > gcd x y         =  gcd' (abs x) (abs y)
> >                    where gcd' a 0  =  a
> >                          gcd' a b  =  gcd' b (a `rem` b)
> >
> > Why is gcd 0 0 undefined?
> >
> > http://en.wikipedia.org/wiki/Greatest_common_divisor says:
> > "It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the
> > natural numbers become a complete distributive lattice with gcd as meet
> > and lcm as join operation. This extension of the definition is also
> > compatible with the generalization for commutative rings given below."
> >
> > An added advantage, for haskell, of defining gcd 0 0 = 0 is that gcd
> > would change from being a partial function to a total function.
> >
> > Regards,
> > Steve