Why is GHC complaining about non-exhaustive patterns?

Question

When I compile the following code with GHC (using the -Wall flag):

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 complains that pattern matching in insert is non-exhaustive:

test.hs|6| 1:
||     Warning: Pattern match(es) are non-exhaustive
||              In an equation for `insert': Patterns not matched: _ (Node _ _ _)

Why is GHC issuing this warning? It is pretty obvious that the pattern GHC complains about is handled in insert x (Node a left right).

Disregard

Answer 1

Riccardo is correct, GHC doesn't infer that your guards can't possibly all be false. So accept his answer please.

I'm going to digress and talk about coding style.

Your motivation for not using otherwise may have been that it looks unsightly:

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)

Looking at this code, a human reader must confirm to themselves that the final guard accepts precisely those cases where x > a.

We could instead write it like this:

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)

The Ordering type returned by compare has only the three values EQ, LT, and GT, so GHC can confirm that you've covered all possibilities, and a human reader can easily see that you've covered them correctly.

This is also more efficient code: we call compare once, instead of calling == and then probably calling < as well.

Now I'm going to digress some more and talk about laziness.

You've probably also written a function similar to this:

contains :: (Ord a) => a -> Tree a -> Bool
contains _ EmptyTree = False
contains x (Node a left right) = case x `compare` a of
    EQ -> True
    ...

When x == a, you need to know that the tree uses the Node constructor, and that its first argument is equal to x. You don't need to know what either of the subtrees are.

But now look back at my definition of insert above. When the tree it's given is a Node, it always returns a Node whose first argument is always a. But it doesn't state that up front: instead it evaluates x `compare` a.

We can rewrite insert to perform the comparison as late as possible:

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

Now we return the Node a bit as soon as possible --- even if the comparison throws an error! --- and we still perform the comparison once at most.

Hux

very interesting digression, especially the part about laziness! And many thanks for supporting my answer :) – Georgeanngeorgeanna

Answer 2

It's because the pattern matching is incomplete. There's no guarantee that one of x==a, x<a, or x>a holds. For instance, if the type is Double and x is NaN then none of them are True.

Implication

My bad, you're right. That's why I deeply hate those ieee standards about dobules :) – Georgeanngeorgeanna

+1 because I didn't know that comparing to NaN always evaluates to false. – Disregard

Interesting that this means compare and <, ==, > are inconsistent for floats (since compare can't say all 3 of those are False; it has to either declare one True in all cases or be partial; I get (sqrt (-1)) `compare` (1/0) == GT). If you take it as a law that they should be consistent, then in fact the OP's pattern match is complete (GHC just doesn't prove it by knowing about the law), and it's a bug that floats either have an Ord instance (or a bug that the Ord instance tries to follow IEEE standards for comparing with NaNs). – Uninterested

The ghc compiler does not assume instances follow any laws. It would be most annoying if it did, since when working with DSLs you often want to make instances that break laws. – Implication

Answer 3

GHC is not able to infer whether your three guards in the insert x (Node a left right) cover all possible cases, and consequently there will be no body to be associated with insert x (Node a left right). Try replacing the last condition x > a with otherwise (a synonim for True). In this specific case however, it's true that the guards do not cover all cases, see augustss' example about double numbers.

Georgeanngeorgeanna