Missing pattern in inserts function

Question

I have this function inserts where

inserts 1 [2,3] = [[1,2,3],[2,1,3],[2,3,1]]

here's the definition (straight from Algorithm Design with Haskell by Bird and Gibbons)

inserts :: a -> [a] -> [[a]]
inserts x [] = [[x]]
inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)

I've tried it in ghci with the example above, but I get the following exception

[[1,2,3],[2,1,3]*** Exception: <interactive>:2:1-53: Non-exhaustive patterns in function inserts

Does anyone know what is the missing pattern?

Answer 1

When I define inserts as per your code and then run inserts 1 [2,3], I don’t get any error, and the correct result is returned. However, I can replicate the error when I do this:

Prelude> inserts x [] = [[x]]
Prelude> inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)
Prelude>
Prelude> inserts 1 [2,3]
[[1,2,3],[2,1,3]*** Exception: <interactive>:2:1-53: Non-exhaustive patterns in function inserts

So the issue is not your function. Rather, you are inputting it into GHCi incorrectly. When you enter a multiline function into GHCi like this, it instead defines two functions rather than one: first it defines inserts x [] = [[x]], and then it overwrites this definition with inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys). The correct method of entering a multiline function into GHCi is instead by surrounding the definition with :{ :}:

Prelude> :{
Prelude| inserts :: a -> [a] -> [[a]]
Prelude| inserts x [] = [[x]]
Prelude| inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)
Prelude| :}
Prelude> inserts 1 [2,3]
[[1,2,3],[2,1,3],[2,3,1]]