使 GCD 代码更好、更简洁

Question

我正在使用欧几里得算法计算 GCD(M,N)，两个整数M 和⟩N的最大公约数。

虽然这段代码运行良好，但我觉得用 max、min 和 abs 来包装两个变量 (a, b) 有点麻烦。

任何人都可以提出一个更好的方法来使代码不那么冗长吗？
我发现内置的 gcd 类型被定义为 gcd :: Integer a => a -> a -> a，但我不能简单地使用它。我需要更改什么才能重用类型定义？

gcd2 :: Int -> Int -> Int
gcd2 a b =
    let x = max (abs a) (abs b)
        y = min (abs a) (abs b)
        in if (y == 0) || (x == y && x > 0) 
           then x 
           else gcd2 y (x-y)

嗯，受到chi的启发，我改了下代码。

gcd3 :: Int -> Int -> Int
gcd3 a b | a <  0 = gcd3 (-a) b
         | b <  0 = gcd3 a (-b)
         | b >  a = gcd3 b a
         | b == a || b == 0 = a
         | otherwise = gcd3 b (a-b)

这是我能做的最好的了。 :)

Answer 1

你可以看看how it is implemented in base:

gcd             :: (Integral a) => a -> a -> a
gcd x y         =  gcd' (abs x) (abs y)
                   where gcd' a 0  =  a
                         gcd' a b  =  gcd' b (a `rem` b)

Answer 2

正如 chi 在他的回答中所建议的那样，为了避免在每个递归步骤中使用 abs，我将定义一个 GCD 局部函数，您可以在其中传递参数的绝对值。这种实现方式非常简单：

gcd :: Int -> Int -> Int
gcd a b = gcd' (abs a) (abs b)
  where gcd' a 0 = a
        gcd' a b = gcd' b (a `mod` b)

使 GCD 代码更好、更简洁

To make the GCD code nicer and less verbose

haskell