主页 / coding / 问题 / 78378607
Accepted
F. Zer
Asked: 2024-04-24 20:52:25 +0800 CST

`gcd` 函数中的模式匹配并不详尽

  • 772

出于学习目的，我用gcd'重复减法来定义函数：

gcd' :: Integer -> Integer -> Integer
gcd' x y 
    | x == y = x
    | x < y = gcd' x (y - x)
    | y < x = gcd' (x - y) y

（Prelude的gcd功能）

问题是 GHC 抱怨它：

模式匹配并非详尽无遗。在‘gcd’的方程中：

“Integer”、“Integer”类型的模式不匹配：_ _

我见过一条关于数字的数学定律：

对于所有数字 𝑥 和 𝑦，𝑥 小于 𝑦，或 𝑦 小于 𝑥，或 𝑥 等于 𝑦。

从这个意义上来说，这三个守卫涵盖了所有可能的情况。为什么 GHC 关注这个定义？

haskell

2 个回答

  1. 正如 Willem 解释的那样，这是因为 GHC 不知道<//>是==可能性的详尽集合。事实上，对于任何布尔值检查，它永远不会知道这一点。

    然而，Haskell 确实有一个替代方案，GHC 能够推断出详尽性：总和类型的模式匹配。这也可以用于根据订单做出决策。你的算法看起来像这样：

    gcd' x y = case compare x y of
   EQ -> x
   LT -> gcd' x (y - x)
   GT -> gcd' (x - y) y

    我想说这实际上比otherwise.

    • 9
  2. Best Answer

    模式匹配并非详尽无遗。gcd在“ ”的等式中：

    问题是 Haskell 并不聪明，知道对于两项x和y，它总是成立x < y，x > y或x == y，而事实上它甚至不成立。事实上，对于 a NaN，它不成立：

    ghci> nan = 0/0
ghci> nan
NaN
ghci> nan == nan
False
ghci> nan > nan
False
ghci> nan < nan
False

    最好使用始终为 true 的条件：otherwise，它是 的别名True：

    gcd' :: Integer -> Integer -> Integer
gcd' x y 
    | x == y = x
    | x < y = gcd' x (y - x)
    | otherwise = gcd' (x - y) y

    请注意，更快的实现gcd'是：

    gcd' :: Integral a => a -> a -> a
gcd' a b
  | b == 0 = a
  | otherwise = gcd' b (a `mod` b)
    • 2

相关问题