Why is init a partial function?

Question

According to the Haskell 2010 report, init is defined as the following:

init             :: [a] -> [a]  
init [x]         =  []  
init (x:xs)      =  x : init xs  
init []          =  error "Prelude.init: empty list"

base-4.4.1.0 defines it similarly. To me, it seems that it would be perfectly acceptable and intuitive to have:

init [] = []

which would make init a total function. Since this definition made it into the haskell 2010 report I guess that there are arguments for it. Is that the case or is it defined that way because of tradition and backwards compatibility?

Answer 1

The same reason tail [] isn't []; it breaks the invariants that define these functions. We can define head and tail by saying that if head and tail are defined for a value xs, then xs ≡ head xs : tail xs.

As Niklas pointed out, the invariant we want to define init and last is xs ≡ init xs ++ [last xs]. It's true that last isn't defined on empty lists either, but why should last be defined if init can't be? Just like it would be wrong if one of head or tail was defined on an input while the other wasn't, init and last are two sides of the same coin, splitting a list into two values that together are equivalent to the original.

For a more "practical" view (although being able to reason about programs in terms of useful invariants about the operations they use has very practical benefit!), an algorithm that uses init will probably not behave correctly on an empty list, and if init worked that way, it would work to hide the errors produced. It's better for init to be conservative about its inputs so that consideration has to be given for edge-cases like empty list when it is used, especially when it isn't at all clear that the proposed value for it to return in those cases is reasonable.

Here's a previous Stack Overflow question about head and tail, including why tail [] doesn't just return []; the answers there should help to explain why these invariants are so important.

Answer 2

Because I find the question interesting, I decided to write down my thoughts on the subject:

Logical

Say we define init xs as "the list, that, if you put last xs on its end, is equal to xs. This is equivalent to: init xs is the list without its last element. For xs == [], there exists no last element, so init [] has to be undefined.

You could add a special case for this, like in "if xs is the empty list, then init xs is the empty list, otherwise init xs is the list, that, if you put last xs on its end, is equal to xs". Notice how this is much more verbose and less clean. We introduce additional complexity, but what for?

Intuitive

init [1,2,3,4] == [1,2,3]
init [1,2,3]   == [1,2]
init [1,2]     == [1]
init [1]       == []
init []        == ??

Note how the length of the lists on the right-hand side of the equations decreases along with the length of the left-hand side. To me, this series cannot be continued in a sensible way, because the list on the right side would have to have a negative size!

Practical

As others have pointed out, defining a special case handling for init or tail for the empty list as an argument, can introduce hard-to-spot errors in situations where functions can have no sensible result for the empty list, but still don't produce an exception for it!

Furthermore, I can think of no algorithm were it would actually be of advantage to have init [] evaluate to [], so why introduce that extra complexity? Programming is all about simplicity and especially Haskell is all about purity, wouldn't you agree?