Pattern matching covering multiple cases

Question

I made a function to compare strings (of course this is an exercise I'm doing in order to learn and I'm well aware that the <, > operators both work with strings in most modern languages). In order to do some recursion I'm using pattern matching for functions, but I'm not really sure on what's going on. Here's my code:

compareStrings :: String -> String -> Char
compareStrings (x:xs) (y:ys)
    | x > y = '>'
    | x < y = '<'
    | x == y = compareStrings xs ys
compareStrings [a] [b]
    | a < b = '<'
    | a > b = '>'
    | a == b  = '='

So, there are a lot of cases I'm not covering in my code, like one empty list and a singleton list, and an empty list and a normal list (multiple elements). And of course its symmetric counterparts. How can I make sure I check them all? Is there something going under the hood or is it just comparing strings (not chars, which was my intention) at some point and I'm not aware of it?

To sum up, my question is: Am I covering all the cases that could arise with my code, and if it's not the case, how could I make sure? And how would I deal with symmetric cases (like first list empty but the second one not, and the other way round) without declaring two different patterns.

The singletons case is redundant, it's enough to compare two empty lists (they are always equal). Once you have that, you are left with just two other cases. — n. 1.8e9-where's-my-share m.
As for symmetric cases, you normally just write them down, this is a bit annoying but not really too much if you keep the number of cases down. — n. 1.8e9-where's-my-share m.

bheklilr bheklilr · Accepted Answer · 2014-06-12T14:30:38

For a problem like this, you're only concerned with the first element of each list, then if the list is empty. In general, you just have to determine what elements of the list your function is operating on and then handle cases until you've covered any kind of list that can be passed in.

For this instance, you want to handle when both lists have data (x:xs) and (y:ys), and when either or both are empty. You can cover this with

-- Both are empty
compareStrings [] [] = '='
-- The first is empty, the second is not
compareStrings [] ys = '<'
-- The first is not empty, the second is
compareStrings xs [] = '>'
-- Both have data
compareStrings (x:xs) (y:ys) = <your current implementation>

Note that in the middle two cases, we didn't have to specify that the list with data actually has data, since if it gets passed the first pattern, then both weren't empty. If you have not (xs == [] && ys == []) && (xs == [] && ys == _) (this is not code, do not attempt to run), then ys is not []. We also didn't have to check the case of xs == [x] && ys == [y] because [x] == x:[] which matches (z:zs) with x == z and [] == zs.

To make sure you do actually cover all patterns, you should enable -fwarn-non-exhaustive-patterns as @StephenDiehl has suggested.

Pattern matching covering multiple cases

2 Answers