29

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).

Noughtmare
  • 9,410
  • 1
  • 12
  • 38
Alexandros
  • 3,044
  • 1
  • 23
  • 37

3 Answers3

52

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.

augustss
  • 22,884
  • 5
  • 56
  • 93
  • 1
    My bad, you're right. That's why I deeply hate those ieee standards about dobules :) – Riccardo T. May 22 '12 at 17:55
  • 1
    +1 because I didn't know that comparing to NaN always evaluates to false. – Alexandros May 22 '12 at 19:16
  • 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). – Ben Sep 22 '17 at 02:13
  • 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. – augustss Sep 24 '17 at 07:15
42

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.

dave4420
  • 46,404
  • 6
  • 118
  • 152
27

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.

Riccardo T.
  • 8,907
  • 5
  • 38
  • 78