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?

CodePudding user response：

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