[Haskell-beginners] Would you shed light on "undefined values" please?

[Brandon Allbery]

On Thu, Jun 23, 2011 at 18:35, Costello, Roger L. <costello at mitre.org> wrote:
>    It follows that there are not two but three Boolean
>    values, namely False, True, and bottom. In fact, every
>    datatype declaration introduces an extra anonymous
>    value, the undefined value of the datatype.
>
> What is the undefined value (bottom) of type Bool?
>
> What is the undefined value (bottom) of type String?

> bottomString = bottomString ++ bottomString

is one way to formulate it.  More generally

> undefined :: a
> undefined = let x = x in x -- a computation that never produces a value

The reason _|_ is significant is that a type that admits it as a value
can be computed lazily.  If your type does not allow for _|_ then it
is strict; anything that touches it in any way when it is invalid (an
infinite loop, exception, or other effect that is not producing an
actual value; this is the effective definition of "bottom") will fail
immediately.  A "lifted" type (one which allows _|_) will only loop /
throw an exception / dump core / set the building on fire / whatever
when something actually demands that value.

Some practical uses of this:

- since _|_ inhabits every lifted type, the definition of "undefined"
that I provided above can be used as a stub during development, and
will always typecheck;

- similarly, the computation

> error :: String -> a

(whose implementation can't be expressed within the language) throws a
runtime exception, and can be used anywhere that a lifted type is
permitted (anywhere, in standard Haskell).

- "undefined" in particular is useful as a placeholder when only the
type is significant.  See "asTypeOf" as an example of this.  (It could
be argued that this case really wants "_" to function as a
pseudo-value instead of just as a pattern, but that has its own
problems.)

> If I create my own datatype:
>
> data MyBool = F | T
>
> What is the undefined value (bottom) of type MyBool?

_|_ is not, in general, expressible within Haskell itself except in
terms of infinite loops or runtime exceptions; it's not like SQL's
NULL, it's a "not-value".  In this case, the easy way to generate a
bottom for your type is

> myBoolBottom :: MyBool
> myBoolBottom = let x = x in x

(Remember that "let" is recursive in Haskell; the above expression
will try to compute "x", which will try to compute "x", which will ...
in reality, the GHC runtime will notice that the computation for "x"
immediately re-enters itself and will compute 'error "<<loop>>"' in
its place, raising a runtime exception.)

GHC and several other Haskell compilers support unlifted types, which
are strict.  Every program uses one, in fact; in GHC, IO is an
unlifted tuple.  The primary explicit use of them is UArray/STArray,
which are the equivalent of arrays in strict languages.

-- 
brandon s allbery                                      allbery.b at gmail.com
wandering unix systems administrator (available)     (412) 475-9364 vm/sms