Is it recommended to always have exhaustive pattern matches in Haskell, even for "impossible" cases?

Question

Is it recommended to always have exhaustive pattern matches in Haskell, even for "impossible" cases?

For example, in the following code, I am pattern matching on the "accumulator" of a foldr. I am in complete control of the contents of the accumulator, because I create it (it is not passed to me as input, but rather built within my function). Therefore, I know certain patterns should never match it. If I strive to never get the "Pattern match(es) are non-exhaustive" error, then I would place a pattern match for it that simply error's with the message "This pattern should never happen." Much like an assert in C#. I can't think of anything else to do there.

What practice would you recommend in this situation and why?

Here's the code:

gb_groupBy p input = foldr step [] input
   where
      step item acc = case acc of
           []                           -> [[item]]
           ((x:xs):ys)                  -> if p x item
                                           then (item:x:xs):ys
                                           else [item]:acc

The pattern not matched (as reported by the interpreter) is:

Warning: Pattern match(es) are non-exhaustive In a case alternative: Patterns not matched: [] : _

Answer 1

This is probably more a matter of style than anything else. Personally, I would put in a

_ -> error "Impossible! Empty list in step"

if only to silence the warning :)

Answer 2

You can resolve the warning in this special case by doing this:

gb_groupBy p input = foldr step [] input
   where
     step item acc = case acc of
        []                           -> [[item]]
        (xs:xss)                      -> if p (head xs) item
                                         then  (item:xs):xss
                                         else [item]:acc

The pattern matching is then complete, and the "impossible" condition of an empty list at the head of the accumulator would cause a runtime error but no warning.

Another way of looking at the more general problem of incomplete pattern matchings is to see them as a "code smell", i.e. an indication that we're trying to solve a problem in a suboptimal, or non-Haskellish, way, and try to rewrite our functions.

Implementing groupBy with a foldr makes it impossible to apply it to an infinite list, which is a design goal that the Haskell List functions try to achieve wherever semantically reasonable. Consider

take 5 $ groupBy (==) someFunctionDerivingAnInfiniteList

If the first 5 groups w.r.t. equality are finite, lazy evaluation will terminate. This is something you can't do in a strictly evaluated language. Even if you don't work with infinite lists, writing functions like this will yield better performance on long lists, or avoid the stack overflow that occurs when evaluating expressions like

take 5 $ gb_groupBy (==) [1..1000000]

In List.hs, groupBy is implemented like this:

groupBy         :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []       =  []
groupBy eq (x:xs)   =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

This enables the interpreter/compiler to evaluate only the parts of the computation necessary for the result. span yields a pair of lists, where the first consists of (consecutive) elements from the head of the list all satisfying a predicate, and the second is the rest of the list. It's also implemented to work on infinite lists.