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

Ответы на вопрос(3)

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

 22 мая 2012 г., 16:23
+1 Пример, почему Риккардо не совсем прав.
 24 сент. 2017 г., 09:15
Компилятор ghc не предполагает, что экземпляры подчиняются каким-либо законам. Было бы очень неприятно, если бы это произошло, поскольку при работе с DSL вы часто хотите создавать экземпляры, нарушающие законы.
 Alexandros22 мая 2012 г., 21:16
+1, потому что я не знал, что сравнение с NaN всегда оценивается как ложное.
 22 сент. 2017 г., 04:13
Интересно, что это значитcompare а также<, ==, > несовместимы для поплавков (так какcompare can't скажем, все 3 из нихFalse; он должен либо объявить одинTrue во всех случаях или быть частичным; я получил(sqrt (-1)) `compare` (1/0) == GT). Если вы принимаете это как закон, что ониshould быть последовательным, тогда фактически соответствие шаблону OPis завершено (GHC просто не доказывает это, зная о законе), и это плавающая ошибка или имеет экземпляр Ord (или ошибка, которую экземпляр Ord пытается следовать стандартам IEEE для сравнения с NaN).
 22 мая 2012 г., 19:55
Мой плохой, ты прав. Вот почему я глубоко ненавижу эти стандарты IEE по поводу dobules :)

GHC не может определить, были ли ваши трое охранников вinsert x (Node a left right) охватить все возможные случаи, и, следовательно, не будет никакого органа, который будет связан сinsert x (Node a left right), Попробуйте заменить последнее условиеx > a сotherwise (синоним дляTrue). In this specific case however, it's true that the guards do not cover all cases, see augustss' example about double numbers.

Решение Вопроса

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

 22 мая 2012 г., 13:39
С помощьюcompare невероятно круто!
 22 мая 2012 г., 12:56
очень интересное отступление, особенно часть о лени! И большое спасибо за поддержку моего ответа :)

Ваш ответ на вопрос