[Haskell-cafe] The values of infinite lists

Bjorn Lisper lisper at it.kth.se
Wed May 10 04:10:21 EDT 2006


>Are the values of infinite lists _|_ (bottom)?

No. _|_ represents total lack of information about the result, whereas in a
lazy language like Haskell an infinite list contains a lot of information:
you can observe arbitrary parts of such a list, access them, and compute
with them.

>In section 1.3, the Haskell 98 report said as follows:
>
>   Errors in Haskell are semantically equivalent to _|_. Technically,
>   they are not distinguishable from nontermination, so the language
>   includes no mechanism for detecting or acting upon errors.

The formulation in the Haskell report is sloppy to say the least, and
clearly misleading as witnessed by your mail. Nontermination is not the
precisely the same as _|_. Only certain kinds of nontermination can be
modeled by _|_ in a non-strict language.

I think one should consider reformulating the paragraph above in future
versions of the Haskell report.

>Therefore, the value of the following infinity is _|_. Right?
>
>   data Nat = Zero | Succ Nat
>
>   infinity = Succ infinity

No. Consider the following function:

f Zero = 0
f (Succ _) = 17

We then have f infinity = f (Succ infinity) = 17, whereas f _|_ = _|_.
Thus, f distinguishes infinity and _|_, so they can not be the same.

>What about infinite lists? For example, is the value of [1 ..] also _|_?

No, see above.

Björn Lisper


More information about the Haskell-Cafe mailing list