Pattern matching incorrect

Question

I'm kinda new to haskell

data Tree a = Leaf | Branch (Tree a) a (Tree a)
  deriving (Show, Eq)

insert :: (Ord a, Eq a) => a -> Tree a -> Tree a
insert x Leaf = Branch Leaf x Leaf
insert x (Branch l v r)
  | x <= v = Branch (insert x l) v r
  | x > v = Branch l v (insert x r)

The code gives the following warning (but compiles):

app\Main.hs:10:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for `insert':
        Patterns not matched:
            _ (Branch Leaf _ Leaf)
            _ (Branch Leaf _ (Branch _ _ _))
            _ (Branch (Branch _ _ _) _ Leaf)
            _ (Branch (Branch _ _ _) _ (Branch _ _ _))
   |
10 | insert x Leaf = Branch Leaf x Leaf
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

Technically speaking x <= v and x > v should cover all possible alternatives, but I'm having this warning. I's actually fixed if I use otherwise in the second case, but shouldn't it work just like this?

By the way, `x <= v` and `x > v` do not cover all the possible alternatives on floating point values. There, we have NaN values and IEEE 754 mandates [both to be false on NaNs](https://en.wikipedia.org/wiki/NaN#Comparison_with_NaN). This is an (in-)famous "feature" which can be very surprising. — chi, Jul 06 '22 at 22:39

score 5 · Accepted Answer · edited Jul 06 '22 at 19:16

An Ord instance should define a total order, but Haskell is unable to enforce that as a requirement nor is it able to detect if an Ord instance is, indeed, a total order.

Prelude> data Foo = A | B deriving Eq
Prelude> instance Ord Foo where _ <= _ = False; _ > _ = False
Prelude> A <= B
False
Prelude> A > B
False

Using otherwise works not because it is True (which it is, by literal definition) when x <= v is False, but because it is True regardless of whether x <= v is true or false. Knowing that <= and > each can return True does not guarantee that one of them will.

Pattern matching incorrect

1 Answers1