How to write Haskell partial functions that will never have invalid values?

Question

Let's say want a function, taking a list of numbers, that returns the sum of adjacent pairs of numbers, except at the two edges where it simply returns the edge numbers. For example:

[1,2,3,4,5] --> [1,3,5,7,9,5]

I come up with the following function:

p1 :: Num a => [a] -> [a]
p1 []         = []
p1 (x:xs)     = x:p2 (x:xs)

p2 :: Num a => [a] -> [a]
p2 [x]        = [x]
p2 (x1:x2:xs) = (x1+x2):p2 (x2:xs)

(never mind if there is a better way to do this ...)

p2 is only ever called by p1. p2 will also never be called with an empty list, only with lists at least one element. However, p2 is still a partial function, and it will trigger a non-exhaustive pattern match warning with ghc -Wall.

What is the accepted way to deal with this? Do I just not write the p2 [] case? Or p2 [] = undefined, or p2 [] = unused_value, or something else?

Answer 1

The most common approach is to put in a final case like

p2 [] = error "impossible! p2 received an empty list"

It should include sufficient information to track down the source of the problem in the error message. It's not ideal, though. People (including me) do it because it's a practical solution to a real problem. But sometimes code evolves and you end up in that case, and figuring out why is a debugging mess.

It's far better to eliminate the problem by changing the boundary conditions to total functions:

p1 :: Num a => [a] -> [a]
p1 xs = zipWith (+) xs' $ tail xs'
  where
    xs' = [0] ++ xs ++ [0]

Now you know that no amount of refactoring can trigger a hidden error case, because there isn't a hidden error case.

Of course this sort of transformation isn't always possible. But it often is, and it's always worth spending a minute searching for. You'll either find a better approach, or have come up with a reason why the function is partial to include in the comments.

Answer 2

You can make p2 total by using a non-empty list type. Or, inlining and uncurrying the standard non-empty list type (a, [a]), you can write something like:

p2 :: Num a => a -> [a] -> [a]
p2 x []      = [x]
p2 x (x':xs) = (x+x'):p2 x' xs

You will of course have to modify p1 slightly to match:

p1 :: Num a => [a] -> [a]
p1 []         = []
p1 (x:xs)     = x:p2 x xs -- the call to p2 on this line changed