[Haskell-cafe] Re: Functional progr., infinity, and the Universe
Nils Anders Danielsson
nad at cs.chalmers.se
Mon Jun 26 08:32:33 EDT 2006
On Sat, 24 Jun 2006, Paul Hudak <paul.hudak at yale.edu> wrote:
> Hmmm... never tried to write all this down in one place before, but I
> think this covers all cases:
> A partial list is one that ends in _|_.
> A total list is one that ends in .
> A finite list is either partial or total.
> Any other list is infinite.
To confuse the picture more I'd like to point out that some use
* A strictly (spine-) partial list is one that ends in _|_.
* A (spine-) total list is one that ends in  or doesn't end at all.
* A finite list is one that ends (with  or _|_).
* An infinite list is one that doesn't end.
The two concepts (finite/infinite and total/strictly partial) are
orthogonal, and both partition the set of all lists.
And of course this generalises to other data types:
Finite: x is finite if it is contained in all ω-chains whose lubs are x.
Infinite: Not finite.
Total: No bottoms.
Strictly partial: Not total.
Partial: Total or strictly partial.
More information about the Haskell-Cafe