[Haskell-cafe] Re: Functional progr., infinity, and the Universe

voigt.16734551 at bloglines.com voigt.16734551 at bloglines.com
Fri Jun 23 10:40:09 EDT 2006

--- paul.hudak at yale.edu wrote:
Jerzy Karczmarczuk wrote:
> > OK, I think
that this subject matured enough to rest in peace...
> I would have to
agree with that, although...

Since the subject is not going to rest, why
not also jump in?
> Well, each partial list is finite. 

I think quite
a few people would agree that a finite list is one ending in []. So 1:_|_
is a partial list, but not a finite one. 1:[] is a finite list.

> But the
limit of a chain IS the maximal element of the set of all 
> elements comprising
the chain, since the LUB, in the case of a chain, is 
> unique, and thus
we don't have to worry about choosing the "least" 
> element (i.e. it reduces
to the upper bound, or maximal element).

That doesn't quite make sense,
IMHO. The chain _|_, 1:_|_, 1:1:_|_, 1:1:1:_|_, ... has the limit (or upper
bound) "ones", but "ones" does not appear in the chain. An upper bound of
a set may not appear in the set. But the maximal element of a set by definition
("element of") necessarily is in the set. So you cannot use the two notions
interchangably. BTW, if the limit of a chain would always appear in the chain
(by virtue of being the  maximal element of the set of all elements comprising
the chain), then every chain would be stationary eventually. That would quite
simplify denotational semantics, wouldn't it?
> So I'd say that Brian
has at least come close to discovering God :-)

And come to the conclusion,
in a later mail, that both:

A. "the list [0,1,2,3,4,5,..] is longer than


B. "ie [0,1,2,3,4,..] is the same length as

I think not. Obviously not. I know that this conclusion was qualified by
"assuming that they all grow at the same rate", which of course has no counterpart
in the denotational semantics setting discussed above. So it's not a wrong
statement, just one that cannot really be formulated.

Well, anyway, didn't
want to be nitpicking. But I think it's important that if we want to think
about Haskell's semantics denotationally (which in itself is somewhat problematic),
we should at least be careful not to blur concepts. And asserting that the
limit of a chain is always an element of that chain is a dangerous oversimplification
that does not work out.

Janis Voigtlaender.

More information about the Haskell-Cafe mailing list