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?
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