Non-exhaustive patterns error when writing recursive list function

Question

In Haskell I want to write a recursive function that for a given list of numbers changes the sign of each element in the sublists:

list = [[1, 3, 6.7, 7.0], [], [1, 8.22, 9, 0]]

multiply (x:xs) = [n * (-1) | n <- x] : multiply xs

but I get an error:

[[-1.0,-3.0,-6.7,-7.0],[],[-1.0,-8.22,-9.0,-0.0]
*** Exception: learning.hs:26:1-48: 
    Non-exhaustive patterns in function multiply

Can anyone tell me, how can I handle an exception with empty sublists?

Answer 1

You've done a phenomenal job of handling the recursive step. But as in any programming language, we also need a base case to terminate recursion. Specifically, you need an explicit case for the []. If given [], you want your function to return [], since there's no more work to be done. Consider

multiply :: Num a => [[a]] -> [[a]]
multiply [] = []
multiply (x : xs) = [n * (-1) | n <- x] : multiply xs

The bottom line is exactly what you've already written. You need the second line to handle [] input. The first line is a type signature, which, while not strictly required, is good design in Haskell and will result in better error messages if something goes wrong.

Answer 2

It's actually not the empty sublist that's the problem:

ghci> multiply [[1, 2, 3], [4, 5, 6]]
[[-1,-2,-3],[-4,-5,-6]*** Exception: <interactive>:2:1-50: Non-exhaustive patterns in function multiply

You handle the sublists with [n * (-1) | n <-x], and list comprehensions work fine on empty lists; this one will just find no elements to multiply by -1 and so will yield an empty list. And you can see the empty list in the output you quoted; it even goes on producing more output afterwards, which is pretty conclusive that it isn't throwing the exception when it's processing the empty sublist.

So what's the problem? Well, let's look at what the error message actually says: Non-exhaustive patterns in function multiply. What that means is that somewhere your code in the function multiply is doing pattern matching, and the value that is being matched doesn't actually fit any of the patterns you've provided. Well, there's only one place in your entire function that does any pattern matching, and that's multiply (x: xs), so that has to be where the problem is!

Now lists are always either the empty list [] or of the form item : rest_of_list (where the : is the other constructor of the list data type). You have only provided a pattern for the : form, so multiply is definitely going to throw an error if you ever apply it to an empty list. That shows us the problem immediately, even without connecting it to what actually happened in your case (which I'll do in a moment).

How to fix it? You need to say what multiply [] should result in. Generally, when you're writing a recursive function of the lists, you want to start with this form:

func [] = _
func (x : xs) = _

And then fill in the blanks. Occaisionally it's convenient to have other cases like [x] or [x, y] if you need to handle lists with 1 or 2 elements specially. Only very rarely should you leave out the case for [], because if you do your function will definitely throw the exception you're seeing in your question for certain calls.

In this case, multiply just negates all of the values in all of the sublists of its list-of-list argument, so it's easy to see what it should do to an empty list of sublists: just return an empty list. So we would have:

multiply [] = []
multiply (x: xs) = [n * (-1) | n <-x]: multiply xs

(If you're entering this into GHCi rather than in a file, you'll need to use multiline mode to enter that; enter :{ to start multiline mode, then enter all of the lines of your definition, then enter :} to give all of the lines of your code to the compiler at once)

---

Now, there's one more obvious question. You didn't call multiply [], you called multiply [[1,3,6.7,7.0],[],[1,8.22,9,0]]. So why is it complaining that the argument doesn't match a pattern for an empty list? The original call doesn't, but every time you called your original multiply it calls itself on a smaller list!

It matches [ [1,3,6.7,7.0], [], [1,8.22,9,0] ] against the pattern x : xs, which results in x = [1,3,6.7,7.0] and xs = [ [], [1,8.22,9,0] ]. Then it calls multiply xs.

So in the second call we're matching [ [], [1,8.22,9,0] ] against the pattern x : xs. In this evaluation, x = [] and xs = [ [1,8.22,9,0] ]. and we call multiply xs again with this version of xs.

Now in the third call we match [ [1,8.22,9,0] ] against the pattern x : xs. For this to succeed we have to find both x and xs. The tail of a single element list is the empty list, so x = [1,8.22,9,0] but xs = []. And then we call multply xs again with this version of xs, and that's where the problem is. Now we try to match [] against the pattern x : xs and we can't, but there are no other patterns to try either, so we just get Non-exhaustive patterns in function multiply.

Answer 3

You can use map with a lambda function wrapping your same list comprehension:

Prelude> list=[[1,3,6.7,7.0],[],[1,8.22,9,0]]
Prelude> map (\x -> [n * (-1) | n <-x]) list
[[-1.0,-3.0,-6.7,-7.0],[],[-1.0,-8.22,-9.0,-0.0]]

Answer 4

You recurse on the tail of the list, this means that eventually you will call multiply xs with xs an empty list, and since you did not specify a case for the empty list, it will raise an error.

If we thus run the code with a list [1,4] we will make a call with multiply [1,4], this will make a recursive call with multiply [4], and that will make a recursive call with [], and then it can not find a pattern to match with the empty list hence the error. This thus means that your function is missing a base-case. We can implement this as:

multiply :: Num a => [[a]] -> [[a]]
multiply [] = []
multiply (x: xs) = [n * (-1) | n <-x] : multiply xs

We however do not need to make use of recursion, in fact we can implement this with map :: (a -> b) -> [a] -> [b] and negate :: Num a => a -> a:

multiply :: Num a => [[a]] -> [[a]]
multiply = map (map negate)

or we can even generalize this further to work with any Functor:

multiply :: (Foldable f, Foldable g, Num a) => f (g a) -> f (g a)
multiply = fmap (fmap negate)