为什么GHC抱怨非详尽的模式

Question

当我使用 GHC 编译以下代码时（使用 -Wall 标志）：

module Main where
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right)
    | x == a = Node a left right
    | x < a = Node a (insert x left) right
    | x > a = Node a left (insert x right)
main :: IO()
main = do
    let nums = [1..10]::[Int]
    print . foldr insert EmptyTree $ nums

GHC抱怨insert中的模式匹配并不详尽：

test.hs|6| 1:
||     Warning: Pattern match(es) are non-exhaustive
||              In an equation for `insert': Patterns not matched: _ (Node _ _ _)

为什么全康会发出此警告？很明显，GHC抱怨的模式是在insert x (Node a left right)中处理的。

Answer 1

这是因为模式匹配不完整。 不能保证x==a、x<a或x>a中的任何一个成立。 例如，如果类型是 Double 并且x是 NaN，则它们都不True。

Answer 2

里

卡多是对的，GHC并没有推断你的守卫不可能都是假的。所以请接受他的回答。

我将离题并谈论编码风格。

您不使用otherwise的动机可能是它看起来难看：

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right)
    | x == a    = Node a left right
    | x < a     = Node a (insert x left) right
    | otherwise = Node a left (insert x right)

查看此代码，人类读者必须向自己确认最终警卫准确地接受那些x > a的情况。

我们可以这样写：

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right) = case x `compare` a of
    EQ -> Node a left right
    LT -> Node a (insert x left) right
    GT -> Node a left (insert x right)

compare返回的Ordering类型只有三个值EQ、LT和GT，因此GHC可以确认您已经涵盖了所有可能性，并且人类读者可以轻松看到您已经正确覆盖了它们。

这也是更有效的代码：我们调用compare一次，而不是调用==然后可能调用<。

现在我要再离题一些，谈谈懒惰。

您可能还编写了类似于以下内容的函数：

contains :: (Ord a) => a -> Tree a -> Bool
contains _ EmptyTree = False
contains x (Node a left right) = case x `compare` a of
    EQ -> True
    ...

x == a时，你需要知道树使用 Node 构造函数，并且它的第一个参数等于 x 。您不需要知道这两个子树是什么。

但是现在回头看看我对insert的定义。当它给出的树是Node时，它总是返回一个Node，其第一个参数总是a。但它没有预先说明：相反，它评估x `compare` a .

我们可以重写insert以尽可能晚地执行比较：

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right) = Node a newLeft newRight
  where comparison = x `compare` a
        newLeft  = if comparison == LT then insert x left  else left
        newRight = if comparison == GT then insert x right else right

现在，即使比较抛出错误，我们也会尽快返回Node a位---！ ---，我们仍然最多执行一次比较。

Answer 3

GHC无法推断出你在insert x (Node a left right)中的三个警卫是否涵盖了所有可能的情况，因此不会有身体与insert x (Node a left right)相关联。尝试将最后一个条件x > a替换为 otherwise（True 的同义词）。然而，在这种特定情况下，警卫确实没有涵盖所有情况，参见奥古斯特斯关于双数的例子。