Non-exhaustive patterns in function compress

Question

I am trying to implement a function called compress such that if a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed. For example:

 λ> compress "aaaabccaadeeee" 

"abcade" 

I have two solutions, compress and compress', that I thought are equivalent. However, compress' works while compress gives the error: "Non-exhaustive patters in function". I thought that compress will cover all cases, but I am not sure what went wrong. Thanks!

compress (x:ys@(y:_))
  | null (x:ys) = []
  | null ys = [x]
  | x /= y = x : compress ys
  | x == y = compress ys

λ\> compress "aaaabccaadeeee"
Non-exhaustive patterns in function compress

compress' (x:ys@(y:_))
  | x == y    = compress' ys
  | otherwise = x : compress' ys
compress' ys = ys

λ\> compress' "aaaabccaadeeee"
"abcade"

Answer 1

Your pattern has two :, meaning it only matches lists with 2 or more elements. You still need definitions for empty and singleton lists:

compress [] = ...
compress [x] = ...

The various guards are all only applied to lists matching the pattern used in the single definition you provide. (In particular, note that null (x:ys) will never be true; null only returns true on [], not any list involving the : constructor.)

In compress', the irrefutable pattern y matches any list not matched by pattern in the first definition.

Answer 2

As already specified in the answer, null (x : ys) can never be True, since we did already do pattern matching with (x:ys@(y:_)), we know the pattern will only "fire" in case the list has at least two elements. We then even construct a new list (x : ys) which means a list that has at least one element x followed by a (non-empty) list ys, so the null check is done on a list that has at least two elements.

We thus need to define different patterns for the empty and singleton list:

compress :: Eq a => [a] -> [a]
compress [] = []
compress [x] = [x]
compress (x:ys@(y:_))
  | x /= y = x : compress ys
  | otherwise = compress ys

We can however boost efficiency and prevent unpacking each node of the list twice with a helper function:

compress :: Eq a => [a] -> [a]
compress [] = []
compress (x:xs) = go xs x
  where go [] x = [x]
        go (x2:xs) x
            | x2 == x = go xs x
            | otherwise = x : go xs x2

Here we thus work with two parameters, and each node in the list is only unpacked once.