When are Haskell guard/ pattern matches considered none exhaustive?

user_15176150 0
Viewed 106

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
conditional-statements pattern-matching haskell
2 Answers

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
user_16710660

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.

user_675790
Related