CODEWITHSUNDEEP
haskellpattern-matching
janreggie
janreggie

Reputation: 434

Pattern match(es) are non-exhaustive for Haskell function without `otherwise` clause

Consider a function disjoint :: (Eq a, Ord a) => [a] -> [a] -> Bool which checks if there exists a common element between two sorted lists (and if it does, it returns False since they wouldn't be disjointed).

disjoint :: (Eq a, Ord a) => [a] -> [a] -> Bool
disjoint [] _ = True
disjoint _ [] = True
disjoint (x:xs) (y:ys)
  | x == y = False
  | x < y = disjoint xs (y:ys)
  | x > y = disjoint (x:xs) ys

In my IDE vscode, it yields the following warning:

Pattern match(es) are non-exhaustive
In an equation for ‘disjoint’: Patterns not matched: (_:_) (_:_)compile(-Wincomplete-patterns)

Writing it in a different yet similar way, by using the otherwise clause, will yield no errors:

disjoint :: (Eq a, Ord a) => [a] -> [a] -> Bool
disjoint [] _ = True
disjoint _ [] = True
disjoint (x:xs) (y:ys)
  | x < y = disjoint xs (y:ys)
  | x > y = disjoint (x:xs) ys
  | otherwise = False

What "pattern" does the first code block "miss"? In other words, at what parameters will the first block of code have problems with?

Upvotes: 2

Views: 473

Answers (2)

Iceland_jack
Iceland_jack

Reputation: 7014

Eq is a superclass of Ord so you can omit it from the constraint.

You can use compare to turn it into data Ordering = LT | EQ | GT which only has three cases, allowing the compiler to infer exhaustiveness.

disjoint :: Ord a => [a] -> [a] -> Bool
disjoint [] _ = True
disjoint _ [] = True
disjoint (x:xs) (y:ys) =
  case x `compare` y of
    EQ -> False
    LT -> disjoint xs (y:ys)
    GT -> disjoint (x:xs) ys

Upvotes: 7

janreggie
janreggie

Reputation: 434

From @chi's comment here:

Consider the following data type:

data TT = Bogus 
instance Eq TT where
  Bogus == Bogus = False
instance Ord TT where
  Bogus <= Bogus = False
  Bogus < Bogus = False
  Bogus >= Bogus = False
  Bogus > Bogus = False

Any comparisons between a Bogus and a Bogus returns False. Because of that,

> disjoint [Bogus, Bogus] [Bogus, Bogus]
*** Exception: Ch04Book.hs:(25,1)-(30,18): Non-exhaustive patterns in function disjoint

The same Exception is raised when running disjoint [acos 2] [acos 2] since comparisons between NaNs always returns False.

Sidenote/implication: A type of typeclass Ord does not necessarily follow the Law of excluded middle. See Bogus where both Bogus < Bogus = False and Bogus >= Bogus = False, and Haskell would not complain.

Upvotes: 3

Related Questions