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

[Paul Hudak]

voigt.16734551 at bloglines.com wrote:
>>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.

1:_|_ is certainly finite.  In what sense is it not?

> 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?

Sorry, see my reply to Bill Wood.  I should have said that the LUB is 
indeed not in the set.  If it WERE in the set, then you simply wouldn't 
have an infinite object.  (In the flat domain of integers, for example, 
every chain consists of exactly two elements: _|_ and n, for each n.) 
But this characteristic is common in domain theory, and is what 
distinguishes what are called "interesting" elements from other elements 
(if I recall the terminology correctly).

> And come to the conclusion, in a later mail, that both:
> 
> A. "the list [0,1,2,3,4,5,..] is longer than [1,2,3,4,5,..]"
> and 
> B. "ie [0,1,2,3,4,..] is the same length as [1,2,3,4,5,..]"
> 
> 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.

My email didn't comment on this issue.  I agree that "growth rate" is 
not relevant when we're talking about "values".  The answer here has to 
do with the cardinality of infinite sets.

> 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.

I agree; sorry about that.

   -Paul