In Haskell, why non-exhaustive patterns are not compile-time errors?

Question

This is a follow-up of Why am I getting "Non-exhaustive patterns in function..." when I invoke my Haskell substring function?

I understand that using -Wall, GHC can warn against non-exhaustive patterns. I'm wondering what's the reason behind not making it a compile-time error by default given that it's always possible to explicitly define a partial function:

f :: [a] -> [b] -> Int
f [] _  = error "undefined for empty array"
f _ []  = error "undefined for empty array"
f (_:xs) (_:ys) = length xs + length ys

The question is not GHC-specific.

Is it because...

• nobody wanted to enforce a Haskell compiler to perform this kind of analysis?
• a non-exhaustive pattern search can find some but not all cases?
• partially defined functions are considered legitimate and used often enough not to impose the kind of construct shown above? If this is the case, can you explain to me why non-exhaustive patterns are helpful/legitimate?

Westley

Answer 1

There are cases where you don't mind that a pattern match is non-exhaustive. For example, while this might not be the optimal implementation, I don't think it would help if it didn't compile:

fac 0 = 1
fac n | n > 0 = n * fac (n-1)

That this is non-exhaustive (negative numbers don't match any case) doesn't really matter for the typical usage of the factorial function.

Also it might not generally be possible to decide for the compiler if a pattern match is exhaustive:

mod2 :: Integer -> Integer
mod2 n | even n = 0
mod2 n | odd n  = 1

Here all cases should be covered, but the compiler probably can't detect it. Since the guards could be arbitrarily complex, the compiler cannot always decide if the patterns are exhaustive. Of course this example would better be written with otherwise, but I think it should also compile in its current form.

Vivisect

Another somewhat common case would be lambda statements inside a guard/case/if branch. You know the argument has a certain form because of which branch you're in, so including it in the lambda is unnecessary. – Superjacent

I don't think it should be written as otherwise. It is a great mod2 definition even if the compiler thinks it is non-exahustive. I arrived at this question because I got this error writting a fib function that should not be defined for negative integers. – Lawyer

maybe this is out of scope, but is deciding whether a pattern match is exhaustive or not related to the halting problem? intuitively it seems like a language that is so strictly typed as haskell should enable this type of analysis, at least for subsets of the language, but I know that gut instincts usually is a horrible way of guessing whether or not something is computable. – Metastasize

Answer 2

You can use -Werror to turn warnings into errors. I don't know if you can turn just the non-exhaustive patterns warnings into errors, sorry!

As for the third part of your question:

I sometimes write a number of functions which tend to work closely together and have properties which you can't easily express in Haskell. At least some of these functions tend to have non-exhaustive patterns, usually the 'consumers'. This comes up, for example in functions which are 'sort-of' inverses of each other.

A toy example:

duplicate :: [a] -> [a]
duplicate [] = []
duplicate (x:xs) = x : x : (duplicate xs)

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates [] = []
removeDuplicates (x:y:xs) | x == y = x : removeDuplicates xs

Now it's pretty easy to see that removeDuplicates (duplicate as) is equal to as (whenever the element type is in Eq), but in general duplicate (removeDuplicates bs) will crash, because there are an odd number of elements or 2 consecutive elements differ. If it doesn't crash, it's because bs was produced by (or could have been produced by) duplicate in the first place!.

So we have the following laws (not valid Haskell):

removeDuplicates . duplicate == id
duplicate . removeDuplicates == id (for values in the range of duplicate)

Now, if you want to prevent non-exhaustive patterns here, you could make removeDuplicates return Maybe [a], or add error messages for the missing cases. You could even do something along the lines of

newtype DuplicatedList a = DuplicatedList [a]

duplicate :: [a] -> DuplicatedList a
removeDuplicates :: Eq a => DuplicatedList a -> [a]
-- implementations omitted

All this is necessary, because you can't easily express 'being a list of even length, with consecutive pairs of elements being equal' in the Haskell type system (unless you're Oleg :)

But if you don't export removeDuplicates I think it's perfectly okay to use non-exhaustive patterns here. As soon as you do export it, you'll lose control over the inputs and will have to deal with the missing cases!

Anthropogenesis

I guess you meant removeDuplicates (x:y:xs) | x == y = x : removeDuplicates xs. – Westley

I hope you don't mind I took the liberty of editing the definition of duplicate as well to match your description of it. e.g. instead of "hello" ↦ "hheelloo" it was incorrectly "hello" ↦ "hhello". – Cruel