Почему 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

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 выше. Когда задано дерево, это 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 2

GHC не может сделать вывод о том, охватывают ли ваши три охранника в insert x (Node a left right) все возможные случаи, и, следовательно, не будет тела, которое должно быть связано с insert x (Node a left right). Попробуйте заменить последнее условие x > a на otherwise (синоним для True). В этом конкретном случае, однако, верно, что охранники не охватывают все случаи, см. Пример августса о двойных числах.

Answer 3

Это потому, что соответствие шаблонов является неполным. Нет никакой гарантии, что один из x==a, x<a, или x>a. Например, если тип Double и x - NaN, то ни один из них не является True.