When are Haskell guard/ pattern matches considered none exhaustive?

Question

I have the following code which defines a function called merge:

merge :: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge [] ys = ys
merge xs [] = xs
merge x y | head x <= head y = x ++ y
          | head x > head y = y ++ x
merge x (y:ys) | head x <= y = x ++ merge [] (y:ys)
               | head x > y = y: merge x ys
merge (x:xs) y | x <= head y = x: merge xs y
               | x > head y = y ++ merge (x:xs) []
merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys)
                    | x > y = y : merge (x:xs) ys

This gives me the following warning:

Patterns not matched:
  [_] [_]
  [_] (_:_:_)
  (_:_:_) [_]
  (_:_:_) (_:_:_)

Looking at my code it's not clear to me what patterns I've missed. What extra patterns should I define to get rid of this warning?

As an aside, this is the same function but implemented with conditionals, this results in no warning. What is the difference between the pattern matched and guarded functions and the conditional function?

merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys

Floating point numbers do not always satisfy one of `x <= y` and `x > y`. Special values like NaNs make both comparisons false. Further, avoid using `head`: pattern matching is safe, while `head` can crash your program if called on an empty list. There's no need to use `head` here. — chi, Jul 19 '22 at 10:58
You can avoid `head` as you did: `merge (x:xs) (y:ys) = ...` will give you access to the heads and match the "both non empty" case. To use guards on top of that, make sure the last guard is ` | otherwise ` (or ` | True`), as the answer below suggests. GHC knows about these two cases and will not emit warnings. Effectively, when generating warnings, GHC will only consider non-guarded patterns or patterns guarded by these two special guards. All other guards are seen by GHC as potentially false, and that can lead to warnings. — chi, Jul 19 '22 at 11:13
Instead of `merge x y | ...` then calling `head x`, write `merge xss@(x:xs) yss@(y:ys) | x <= y = xss ++ yss` -- i.e. `xss` on rhs refers to the whole list. But do you really want to concat those lists based only on comparing their heads? That contradicts the last 2 equations -- which is unreachable BTW. (And the first 2 equations duplicate.) — AntC, Jul 19 '22 at 11:16

Micha Wiedenmann · Accepted Answer · 2022-07-19T11:43:18.457

4

The compiler does not know that your guard conditions handle all the cases. Instead of

merge x y | head x <= head y = x ++ y
          | head x > head y  = y ++ x

you could use True

merge x y | head x <= head y = x ++ y
          | True             = y ++ x

or more idiomatic using otherwise (which is just another name for True):

merge x y | head x <= head y = x ++ y
          | otherwise        = y ++ x

edited Jul 19 '22 at 11:43

answered Jul 19 '22 at 10:48

Micha Wiedenmann

19,979
21
92
137

Would making the change you suggested ensure every condition is covered? – Connor Jul 19 '22 at 11:07
1

Who said `True` was another name for `otherwise`? It is [`otherwise`](https://hackage.haskell.org/package/base-4.16.2.0/docs/src/GHC.Base.html#otherwise). – Micha Wiedenmann Jul 19 '22 at 11:45
2

@Connor: `otherwise` is an alias for `True`, not the other way. – Willem Van Onsem Jul 19 '22 at 11:49
In code-golf you frequently also see something like [`1<2`](https://codegolf.stackexchange.com/a/25430/24877) instead of `otherwise`! – flawr Jul 19 '22 at 14:47
Another good option is `case head x <= head y of False -> ...; True -> ...` or similar. (Common variants include `if` instead of `case` and `compare`/`GT`/`_` instead of `<=`/`False`/`True`.) – Daniel Wagner Jul 19 '22 at 21:01

score 2 · Answer 2 · answered Jul 19 '22 at 11:48

2

As explained, head x <= head y and head x > head y are not always each others opposite. Indeed, if we for example work with NaN, we see:

ghci> nan = 0 / 0
ghci> nan >= nan
False
ghci> nan < nan
False

so both fail. Likely your head x > head y should simply always succeed if the previous case fails. We can use otherwise for this, or True: a condition that is always true.

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
    | x <= y = …
    | otherwise = …

Here you need to rewrite the … parts. Using x ++ y and y ++ x was not sufficient: since we need to recurse on the (tail of the) lists and merge these as well.

Please do not use head :: [a] -> a and tail :: [a] -> [a]: these are not total: for an empty list these will error. By making use of the pattern (x:xs) we here got a reference to the head x and the tail xs and the line will only "fire" if it is indeed a non-empty list.

answered Jul 19 '22 at 11:48

Willem Van Onsem

443,496
30
428
555

Doesn't the function type `Ord => a` prevent `nan` being included? – Connor Jul 19 '22 at 12:28
@Conner: no, `Ord` only means that you can call `<`, `>=`, etc. on values of that type. – Willem Van Onsem Jul 19 '22 at 12:40
Okay, and `nan` falls into that category? – Connor Jul 19 '22 at 12:56
@Conner: `nan` has type `Double` (or `Float`) or another `Floating` type, `Double` and `Float` are instances of `Ord` yes. – Willem Van Onsem Jul 19 '22 at 13:02
Theoretically, `Ord` is supposed to represent a total order, and the presence of NaN values means that `Double` and `Float` are *not* total orders. Practically, it makes more sense to ignore NaN and treat the types as if they *were* total orders. – chepner Jul 20 '22 at 15:39

When are Haskell guard/ pattern matches considered none exhaustive?

2 Answers2