Re: [Haskell-cafe] Re: Functional progr., infinity, and the Universe
OK, I think
--- paul.hudak@yale.edu wrote: Jerzy Karczmarczuk wrote: 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.
But the
elements comprising
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. limit of a chain IS the maximal element of the set of all 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 [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. 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. Ciao, Janis Voigtlaender.
voigt.16734551@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
On Fri, Jun 23, 2006 at 10:57:48AM -0400, Paul Hudak wrote:
voigt.16734551@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?
And what is length _|_ ?
Stepan Golosunov wrote:
On Fri, Jun 23, 2006 at 10:57:48AM -0400, Paul Hudak wrote:
voigt.16734551@bloglines.com wrote:
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?
And what is length _|_ ?
_|_, of course!! :-) The point being, length is well-defined only for total lists; it is undefined for partial lists. But this doesn't mean that a partial list isn't finite. -Paul
On Fri, Jun 23, 2006 at 03:30:18PM -0400, Paul Hudak wrote:
Stepan Golosunov wrote:
On Fri, Jun 23, 2006 at 10:57:48AM -0400, Paul Hudak wrote:
voigt.16734551@bloglines.com wrote:
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?
And what is length _|_ ?
_|_, of course!! :-)
The point being, length is well-defined only for total lists; it is undefined for partial lists. But this doesn't mean that a partial list isn't finite.
What is "finite list" then? Is ones = 1:ones also finite?
Stepan Golosunov wrote:
1:_|_ is certainly finite.
And what is length _|_ ?
_|_, of course!! :-)
The point being, length is well-defined only for total lists; it is undefined for partial lists. But this doesn't mean that a partial list isn't finite.
What is "finite list" then? Is ones = 1:ones also finite?
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. So "ones" is infinite. -Paul
On Sat, 24 Jun 2006, Paul Hudak
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 different terminology: * 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. -- /NAD
participants (5)
-
Nils Anders Danielsson -
Paul Hudak -
Stefan Holdermans -
Stepan Golosunov -
voigt.16734551＠bloglines.com