Почему GHC жалуется на неисчерпывающие шаблоны?

Когда я скомпилирую следующий код с 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).

Ответ 1

Риккардо прав, 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 как можно скорее --- даже если сравнение вызывает ошибку! --- и мы по-прежнему выполняем сравнение как можно больше.

Ответ 2

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

Ответ 3

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