29

当我用 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 会发出此警告？很明显，GHC 抱怨的模式是在insert x (Node a left right).

4

3 回答 3

52

这是因为模式匹配不完整。不能保证x==a、x<a或之一x>a成立。例如，如果类型是Double并且x是 NaN，那么它们都不是True.

于 2012-05-22T12:39:26.573 回答
42

Riccardo 是正确的，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)

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

这也是更高效的代码：我们调用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上面的定义。当它给出的树是 aNode时，它总是返回 a ，它Node的第一个参数是 always 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尽快返回该位 --- 即使比较抛出错误！--- 我们仍然最多执行一次比较。

于 2012-05-22T10:03:27.267 回答
27

GHC 无法推断出你的三个后卫是否insert x (Node a left right)覆盖了所有可能的情况，因此不会有任何身体可以关联insert x (Node a left right)。尝试用（的同义词）替换最后x > a一个otherwise条件True。但是，在这种特定情况下，守卫确实不能涵盖所有情况，请参见augustss关于双数的示例。

于 2012-05-22T09:51:20.823 回答