Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why Haskell uses bottom instead of null in partial functions?

Tags:

types

haskell

I'm reading about Haskell denotational semantics (http://en.wikibooks.org/wiki/Haskell/Denotational_semantics) and I fail to see why, in a type, bottom "value" is placed at another level compared to "normal" values, eg why it can't be pattern matched.

I believe that pattern patching bottom would cause trouble as bottom denotes also non-terminating computations, but why should non-terminating computations and errors be treated the same? (I'm assuming calling a partial function with unsupported argument can be considered as an error).

What useful properties would be lost, if all Haskell types included a pattern-matchable Java-null-like value instead of bottom?

In other words: why wouldn't it be wise to make all Haskell functions total by lifting all types with null value?

(Do non-terminating computations need a special type at all?)

like image 837
Aivar Avatar asked Feb 03 '13 20:02

Aivar


2 Answers

You can't get rid of non-termination without restricting the turing-completeness of your language, and by the halting problem, we can't generally detect non-termination and replace it by a value.

So every turing complete language has bottom.

The only difference between Haskell and Java is then that Java has bottom and null. Haskell doesn't have the latter, which is handy because then we don't have to check for nulls!

Put another way, since bottom is inescapable (in the turing complete world), then what's the point of also making everything nullable too, other than inviting bugs?

Also note that while some functions in the Prelude are partial for historic reasons, modern Haskell style leans towards writing total functions nearly everywhere and using an explicit Maybe return type in functions such as head that would otherwise be partial.

like image 139
sclv Avatar answered Sep 24 '22 05:09

sclv


My quibbling in the comments not withstanding, I think sclv answers the first part of your question, but as to

What useful properties would be lost, if all Haskell types included a pattern-matchable Java-null-like value instead of bottom?

In other words: why wouldn't it be wise to make all Haskell functions total by lifting all types with null value?

Here you appear to be drawing a distinction between non-termination and exception. So, although it is impossible (because of the halting problem) to pattern match on non-termination, why not be able to pattern match on exception?

To which I reply with a question of my own: what about functions that never throw an exception? Haskell has total functions after all. I shouldn't have to pattern match to ensure that something is non-exceptional, if it is known to be non-exceptional. Haskell, being a bondage and discipline language, would naturally want to communicate this difference in the types. Perhaps by writing

Integer

for the type of Integers that are known to be not exceptional and

?Integer

for the type of Integers that might be an exception instead. The answer is we do this already: Haskell has a type in the prelude

data Maybe a = Just a | Nothing

which can be read as "either an a or nothing at all." We can pattern match on Maybe so this proposal doesn't give us anything. (We also have types like Either for richer kinds of "computations that might go wrong" as well as fancy monad syntax/combinators to make these easy to work with).

So then, why have exceptions at all? In Haskell we can't "catch" exceptions except in the IO monad. If we can simulate exceptions perfectly with Maybe and Either why have exceptions in the language?

There are a couple of answers to this, but the core is that Haskell exceptions are imprecise. An exception might arise because your program ran out of memory, or the thread you were executing got killed by another thread, or a whole host of other non-predictable reasons. Further, generally with exceptions we care which exception we get out. So what should the following expression result in?

(error "error 1") + (error "error 2") :: Integer

this expression should clearly result in an exception, but which exception? (+) specialized to Integer is strict in both arguments, so that isn't going to help. We could just decide that it was the first value, but then in general we would have

x + y =/= y + x

which would limit our options for equational reasoning. Haskell provides a notion of exceptions with imprecise behavior, and this is important since the pure part of the language has perfectly precise behavior and that can be limiting.

like image 41
Philip JF Avatar answered Sep 22 '22 05:09

Philip JF