为什么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会发出此警告？很明显,GHC抱怨的模式是在处理中的insert x (Node a left right).

Answer 1

这是因为模式匹配不完整.有没有保证的一个x==a,x<a或x>a持有.例如,如果类型是Double和xNaN,那么它们都不是True.

Answer 2

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,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上面的定义.当它给出的树是a时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(一个synonim True).然而,在这个特定的情况下,卫兵确实没有涵盖所有情况,请参阅augustss关于双数的例子.