Why is Haskell `head` broken into an empty list (or why * does not * return an empty list)? (Philosophy of language)

Question

Note to other potential participants: Please feel free to use abstract or mathematical notation to make your point. If I find your answer unclear, I will ask for clarification, but otherwise you can express yourself in a convenient manner.

To be clear: I'm not looking for a "safe" head , and the choice of head in particular is exceptionally significant. The meat of the question follows the discussion of head and head' , which serve to provide context.

I’ve been hacking Haskell for several months (to the point that it has become my main language), but I’m admittedly not well informed about some of the more advanced concepts and details of the philosophy language (although I’m more than ready to learn). My question then is not so technical (if it is not, and I just do not understand), since he is one of the philosophers.

In this example, I'm talking about head .

As I understand it, you will know

 Prelude> head [] *** Exception: Prelude.head: empty list 

This follows from head :: [a] -> a . Fair. Obviously, you cannot return an element (without the slightest) type. But at the same time, it’s easy (if not trivial) to define

 head' :: [a] -> Maybe a head' [] = Nothing head' (x:xs) = Just x 

I saw a little discussion of this here in the comments section of some statements. Noteworthy that one alex stangle says

“There are good reasons not to make everything“ safe ”and throw exceptions when preconditions are violated.

I do not necessarily doubt this statement, but I am curious what these "good reasons" are.

In addition, Paul Johnson says:

'For example, you can define "safeHead :: [a] → Maybe a", but instead of processing an empty list or proving that this cannot be, you need to process "Nothing" or prove that it can "Listen" .

The tone I read from this comment suggests that this is a noticeable increase in complexity / complexity / something, but I'm not sure I understand that it is there.

One Stephen Pruzina says (in 2011, at least)

"There's a deeper reason why, for example, a head cannot be crash proof. To be polymorphic, but to process an empty list, the head should always return a variable of a type not found in any particular empty list. That would be Delphi, if Haskell could do this ... "

Is polymorphism lost by allowing empty list processing? If so, how and why? Are there any special cases that will make this obvious? There is enough response from @Russell O'Connor in this section. Any further thoughts are, of course, appreciated.

I will edit this as clarity and sentence dictate. Any thoughts, documents, etc. that you can provide will be most valuable.

Answer 1

Is polymorphism lost by allowing empty list processing? If so, how and why? Are there any special cases that make this obvious?

The free theorem for head states that

 f . head = head . $map f 

Applying this theorem to [] , it follows that

 f (head []) = head (map f []) = head [] 

This theorem must hold for every f , therefore, in particular, it must hold for const True and const False . It means that

 True = const True (head []) = head [] = const False (head []) = False 

Thus, if head is properly polymorphic and head [] is the full value, then True will be False .

PS. I have other comments about the background of your question, if you have a precondition that your list is not empty, then you must enforce it using the non-empty list type in your function signature, and not using the list.

Answer 2

Why does someone use head :: [a] -> a instead of matching the pattern? One reason is that you know that the argument cannot be empty and does not want to write code to handle the case when the argument is empty.

Of course, your head' type [a] -> Maybe a is defined in the standard library as Data.Maybe.listToMaybe . But if you replace using head with listToMaybe , you must write code to handle the empty case that defeats this goal when using head .

I am not saying that using head is a good style. This hides the fact that this can lead to exclusion, and in this sense it is not good. But sometimes it’s convenient. The fact is that head serves some purpose that listToMaybe cannot serve.

The last quote in the question (about polymorphism) simply means that it is impossible to define a function of type [a] -> a , which returns a value in an empty list (as Russell O'Connor explained in his answer ).

Answer 3

It is natural to expect the following: xs === head xs : tail xs - the list is identical to the first element, followed by the rest. Seems logical, right?

Now count the number of matches (appendices : , ignoring the actual elements when applying the stated “law” to [] : [] should be identical to foo : bar , but the former has 0 conses, and the latter has (at least) one. Oh, oh, something is not here!

A system like Haskell, for all its strength, cannot express the fact that you should only call head in a non-empty list (and that the "law" is only valid for non-empty lists). Using head transfers the burden of proof to the programmer, who must make sure that he is not used in empty lists. I believe typed languages ​​like Agda can help here.

Finally, a slightly more operational philosophical description: how to implement head ([] :: [a]) :: a ? Overcoming a type a value from thin air is not possible (think of uninhabited types such as data Falsum ) and will mean something to prove (through the Curry-Howard isomorphism).

Answer 4

There are several ways to think about it. Therefore, I will argue against and against head' :

Against head' :

There is no need to have head' : since lists are a specific data type, everything you can do with head' you can do with pattern matching.

Also, with head' you simply trade one functor for another. At some point you want to go to the brass keys and do some work on the main element of the list.

In defense of head' :

But pattern matching obscures what is happening. At Haskell, we are interested in computing functions that are better done by writing them in a dot-free style using compositions and combinators.

In addition, thinking about functors [] and Maybe , head' allows you to move between them (in particular, Applicative instance [] with pure = replicate .)

Answer 5

If in your use case an empty list doesn't make sense at all, you can always use NonEmpty , where neHead is safe to use. If you see this from this angle, this is not a head function that is unsafe, it is a whole list data structure (again for this use case).

Answer 6

I think this is a matter of simplicity and beauty. This, of course, is in the eye of the beholder.

If you use the Lisp background, you may know that lists are built from cons cells, each cell has a data element and a pointer to the next cell. An empty list is not a list as such, but a special symbol. And Haskell comes with this reasoning.

In my opinion, it is cleaner, easier to reason and more traditional, if an empty list and a list are two different things.

... I can add - if you are worried that the head is unsafe - do not use it, use pattern matching instead:

 sum [] = 0 sum (x:xs) = x + sum xs