Non-exhaustive pattern matching?

Question

I have the following code:

data Tree = Leaf | Node Int Tree Tree
  deriving (Eq, Show, Read, Ord)

insert :: Int -> Tree -> Tree
insert n Leaf = Node n Leaf Leaf
insert n tree@(Node num lt rt)
                    | n < num  = Node num (insert n lt) rt
                    | n > num  = Node num lt (insert n rt)
                    | n == num = tree

To me, the insert function seems to be exhaustive wrt the possible parameter patterns but when I try to compile with ghc, it says

Pattern match(es) are non-exhaustive
In an equation for ‘insert’:
    Patterns not matched:
        _ (Node _ Leaf Leaf)
        _ (Node _ Leaf (Node _ _ _))
        _ (Node _ (Node _ _ _) Leaf)
        _ (Node _ (Node _ _ _) (Node _ _ _))

Can you help me see why?

Willem Van Onsem · Accepted Answer · 2021-09-15T18:22:53.167

4

Haskell does not know that if n < num does not hold and n > num does not hold, that n == num holds. @Noughtmare points out that for floating point numbers like Float and Double this is not the case (although strictly speaking the definition of Ord for floating point numers does not define an order relation).

You can use otherwise (which is an alias for True) which means that regardless how n and num relate will "fire" the last guard; or we can make use of compare and exhaustively define all cases:

insert :: Int -> Tree -> Tree
insert n Leaf = Node n Leaf Leaf
insert n tree@(Node num lt rt) = go (compare n num)
  where go LT  = Node num (insert n lt) rt
        go GT = Node num lt (insert n rt)
        go EQ = tree

edited Sep 15 '21 at 18:22

answered Sep 15 '21 at 17:14

Willem Van Onsem

443,496
30
428
555

It is not only that GHC doesn't know it, it just isn't always the case that `x > y`, `x < y` and `x == y` cover all cases, take for example `x = 0/0 :: Double` and `y = 0/0 :: Double`. – Noughtmare Sep 15 '21 at 17:37
@Noughtmare: yes, but actually the `instance Ord` of a `Double` does not satisfy the requirements of an order relation, since it is not reflexive. Strictly speaking, `Double` should perhaps not be an instance of `Ord`. As the documentation explains `x <= x` should always be `True`, but as you say, `Double` does not respect that. – Willem Van Onsem Sep 15 '21 at 17:38
@Noughtmare: but I guess floating point numbers are a weak spot in Haskell's `base` package. For example `[5.2 ..]` each time adds one to the value, this means it can get stuck in an infinite loop (if one no longer can be represented by the mantissa), and it also does not enumerate over all possibilities. Perhaps it had been worth to define a special class for order relations/... for floating points. – Willem Van Onsem Sep 15 '21 at 17:43
@WillemVanOnsem Are you sure? In ghci, I see `2^53 == 2^53 + 1.0` -> `True`, but (say) `last [2^53 .. 2^53+5.0]` terminates. – Daniel Wagner Sep 15 '21 at 19:43
@DanielWagner: locally `length [2**128 .. 2**128 + 100 ]` seems to get stuck in an infinite loop (seem with `last ...`), or at least it does not return anything in a sensical amount of time. – Willem Van Onsem Sep 15 '21 at 19:52
@WillemVanOnsem Check out `length [2^n .. 2^n+1.0] | n <- [53..]]`. I have no explanation for the result, but it does seem to suggest that your query would finish if you waited long enough... you know, just long enough to generate 100*2^128 `Double`s... ezpz – Daniel Wagner Sep 15 '21 at 19:54
@WillemVanOnsem Ah, actually, I do have a possible explanation, which reduces the amount of time you have to wait by a factor of 100*2^53 or so compared to my previous estimate: I bet it's actually computing an offset in the precise world, then converting to `Double`, then adding, then comparing. So you'd have to wait until the offset was big enough to be representable in the mantissa (about 2^(128-53) steps), but then that difference would easily be bigger than 100 and stop. (So `[2^128 .. 2^128+1]` and `[2^128 .. 2^128+100]` are probably the exact same list for `[Double]`.) – Daniel Wagner Sep 15 '21 at 20:05
@DanielWagner: I remember a few years ago that there was a discussion about `Enum` for `Double` that at least made it clear that `Enum` was not implemented very sensical. If I recall correctly, the Haskell report said that for float-like numbers, the step is always `+1`, not the *next representable value* (which probably is not very useful, but perhaps more consistent with how an `Enum` is supposed to look). I'm not sure if the `Enum` implementation has been changed since then, – Willem Van Onsem Sep 15 '21 at 20:05

Non-exhaustive pattern matching?

1 Answers1