Haskell pattern not matched [_]

Question

I have been trying to make the following code work:

{-# OPTIONS_GHC -fwarn-incomplete-patterns #-}
import Data.List
format :: String -> String
format [] = []
format (a:b:xs)
 | a == 'W' && b == 'U' = " " ++ format (drop 1 xs) 
 | otherwise = a : format (b:xs)

songDecoder :: String -> String
songDecoder xs = unwords. words . format $ xs

When I test with:

songDecoder "AWUBBWUBC"

I expect "ABC" as output. However, I'm getting an unusual pattern matching warning:

Pattern match(es) are non-exhaustive
In an equation for ‘format’: Patterns not matched: [_]

I'm not sure why I need to match [_] when I have

format (a:b:xs)

Please help.

Answer 1

Like @EricFulmer writes in his answer, (a:b:xs) matches lists with two or more items. So your function works as:

format [] = ...       -- empty list
format (a:b:xs) = ... -- two or more

And Haskell is warning that a list with one element [_] will not match any of these lines: both patterns will fail.

You thus should add a clause, to specify what should happen in the case the list contains one element, for instance (and probably):

format a@[_] = a

Where @ is an alias operator and it binds with a list with exactly one element.

In full we then obtain:

format :: String -> String
format [] = []
format a@[_] = a
format (a:b:xs)
 | a == 'W' && b == 'U' = " " ++ format (drop 1 xs) 
 | otherwise = a : format (b:xs)

We can make the function more elegantly, by by moving the comparisons into the pattern matching:

format :: String -> String
format [] = []
format a@[_] = a
format ('W':'U':xs) = format $ drop 1 xs 
format (a:b:xs) = a : format (b:xs)

Now the last case can be simplified into:

format (a:xs) = a : format xs

and now the second clause (our format a@[_]) becomes obsolete, since the last clause handles that case as well. So we turn the function into:

format :: String -> String
format [] = []
format ('W':'U':xs) = format $ drop 1 xs 
format (a:xs) = a : format xs

Personally I think this is is more elegant since here it is clear what you aim to match with the second pattern (you do not have to write a sequence of conditions). Furthermore one can almost syntactically see that the function handles all possible inputs.

Answer 2

In the pattern (a:b:xs), you're only matching lists of length >= 2. You're missing a pattern for a one-item list.

For example, these match (a:b:xs):

1. "AWUBBWUBC" -- a is bound to "A", b is bound to "W", and xs is bound to "UBBWUBC" (syntactic sugar for 'U':'B':'B':'W':'U':'B':'C':[]).
2. "AWU" -- a and b are bound as above, but xs is now bound to "W".
3. "AW" -- a and b are again bound to "A" and "W" respectively.

Something like "A" wouldn't because you could bind a to "A" and xs to the empty list, but you don't have anything for b.

I hope this explains it!