Hans Aberg <[EMAIL PROTECTED]> writes:
> I think that the original problem is due to the fact that Haskell does not
> know how to handle ordinals properly:
>
> Let S be the set of countable finite ordinals; if w = \omega is the first
> countably infinite ordinal and N the set of natural numbers, then S can be
> identified with N[w], the set of polynomials with coefficients in the set
> of natural numbers. The set S is well ordered. If A is a set, then an at
> most countably infinite list l with values in A can be viewed as a map l: I
> -> A, where I is an interval of S containing 0 (the smallest element of S).
>
> Now look at
> l = [(x, y) | x <- [0..], y <- [0..] ]
> which in Hugs produces the output
> [(0,0),(0,1),(0,2),(0,3),(0,4) ....
> without ever terminating or exhausting the first variable. But if lists are
> defined as merely maps N -> A, then this object is not even well defined as
> a list: we have failed to set up a proper function defining the list.
>
> However, using the definition using ordinals above, we can define l as the map
> a + b w |-> (a, b)
> which is clearly well defined. One can similarly concatenate infinite lists.
>
> So now the problem is no longer how to properly create the infinite list,
> but how to properly print it out once it has been created. That consists of
> finding a suitable projection pi: N -> I subset S = N[w], and then print
> l_pi(i), i = 0,1,2, ...
Well, the problem is not just printing it out, but doing anything with
the list. In your example
l = [(x, y) | x <- [0..], y <- [0..] ]
or
a + b w |-> (a, b)
do you want l to have the type [(Integer,Integer)] ? If not, what
type should it have?
If l does have type [(Integer,Integer)], then it is essentially
equivalent to
l' = [(0, y) | y <- [0..] ]
The only operations available in Haskell on lists are check for empty
list, take the head, and take the tail; no number of applications of
these operations can distinguish l and l'.
> But point is that the different possible choices of projection pi does not
> affect the mathematical object l.
Is there any point in having different mathematical objects l and l'
when no Haskell program could distinguish them?
Carl Witty
[EMAIL PROTECTED]
