>You can define is very easily: two lists are equal if the ith element of
>one list is equal to the ith element of the other list, for all valid
>indices i.
The problem is that you've slipped subtly from a well-known creature, like
1..10, a finite set of ten distinct integers, to a quite a different sort
of beast entirely, 1..Inf, which while notationally similar to the first,
does not share some very fundamental properties. For example, it no longer
has an integral membership count, that is, a length. This is problematic
if one is not quite careful.
>As for whether you can *evaluate* this test in bounded time, that depends.
>Computers are incapable of storing truly infinite lists, so the lists will
>have finite internal representations which you can compare.
Is it possible that "finite internal representations" will differ in
internal representation yet produce identical series? It seems to me that
some meta-analsys would be required if this is possible. If it is not
possible, then that means that every distinct series has a distinct
internal representation. Certainly this is not true lexically: I can
use many variant lexical representations to produce the same infinite
series. For example:
(1 .. X, X+1 .. Inf)
(1 .. Y, Y+1 .. Inf)
Those define identical list, for any natural numbers X and Y, even as
compile-time constants. However, save for special case of X==Y, I do
not expect their internal representation to be the same.
>As for two dynamically generated infinite lists (which you can't easily
>compare, for example if they're based on external input)... it will either
>return false in finite time, or spend infinite time on determining they're
>indeed equal.
I suppose you could classify
(1 .. X, X+1 .. Inf)
(1 .. Y, Y+1 .. Inf)
as "dynamically generated infinite lists", but again, given constants X and
Y, they really needn't be. Even a run-time thing like the list (1 .. $X)
shouldn't actually need to spend infinite time on determining its
equivalence to (1 .. $Y). However, there are more interesting
possibilities: generic iterator functions that you repeatedly call and
which produce successors that aren't generally recognizable. Remember the
old flipflop, as in
if ( 1 .. /^$/ ) { }
if ( /foo/ .. /bar/ ) { }
if ( f() .. g() ) { }
You could, a think, have an infinite list that was really some fancy
interface to a dynamic interator of some sort. I know it's interesting,
but whether this would be sufficiently useful to justify its complexity is
rather less obvious. But if you did have such a list, where stepping
down it implicitly called some sort of ->ITER method or whatnot, then
for those I could see the intractability of finite evaluation, since it's
perfectly conceivable that it wouldn't terminate. Another pitfall is
non-reproduceability; think about readline() as an <iterator> on a stream
object whose underlying file descriptor is not seekable. But I'm not sure
that the any of the sorts of lists we've been talking about have to have
that problem. But I don't know whether we can be clever enough to step
around infinite evaluation through some sort of higher-level analysis.
A clever compiler could move things around. Maybe it could change
for ($i = 1; $i <= 10_000; $i++)
into
for $i ( 1 .. 10_000 )
and then perhaps take advantage of that construct's lazy evaluation.
Given general purpose lazy evaluation, you could start doing things
like thinking of
for ($i = 1; $i <= fn(); $i++)
for $i ( 1 .. fn() )
and making instead a list or array whose members are
( 1 .. fn() )
However, do you evaluate fn() only once or repeatedly?
Hm.
If it were repeatedly, then I do see what you mean by dynamically
generated infinite lists.
>>In other words, if you treat Inf as any particular number (which Mr
>>Mathematician stridently yet somewhat ineffectually reminds you that are
>>*not* allowed to do!), then you may get peculiar results.
>There is no problem with doing that, as long as you define what you want
>it to do.
Well, sure, you could let Inf = MAXINT + 1 for example, and then define
things as you want them to act, but that doesn't mean that this resulting
Inf is either what people think of as a Number nor what they think of as
Infinity. See below on IEEE, which found it very useful to something of
the like.
>Remember, most of mathematics is just an invention of humans :)
I believe we are indeed trying to define what we want it to do, no?
So sure, you can create a new infinite set by conjoining some new elements
to an existing one. That's what all the numberic sets are, pretty much.
Do be careful that the result has consistent properties, though.
>>(crap about testing first/last N elements)
>testing the first/last N elements is not the same as testing the whole list
>for all N :)
>>Mr Mathematician, purist that he is, has of course long ago thrown up his
>>hands in disgust, contempt, or both, and stormed out of the room
>If he has, he's a very narrow-minded Mr Mathematician
>>how can you say 1+Inf?
>Unless you're speech-impaired, it's not too hard
Theoretically, one cannot speak of a number greater than infinity, because
"greater than" is an operation that is defined only upon numbers, and
infinity is not a number. Practically, IEEE has defined constants called
Inf and NaN. Certain operations produce them (or sometimes -Inf). But
most of the Laws of Arithmetic as you and I know them do not apply to these
values. (One could say as much for floating-point numbers, I suspect.) It
stands up to certain operations, like the arithmetical identity (+0) or the
multiplicative one (*1), but every number acts simultaneously as the
arithmetical identity and the multiplicative identity when applied to IEEE
Inf. By this you can already infer that there are many laws that do not
apply. Here's one: under the set of integers, the operation N+1 must
produce a number that is distinct from N. This is not true with IEEE Inf;
there, Inf+1 == Inf. Another bit of common sense is that the operation
0+N-N should under integers always yield 0. It does, for all integers, but
not for Inf. Under IEEE, subtracting Inf from Inf produces not zero but
NaN. (Integers aren't all that pristine, of course: 1*N/N does not yield 1
for all N, of course; N might be 0. And it's not the computer's fault. :-)
>>and 1..Inf will be problematic, too, since to say 1..Inf is also to say
>>there must exist some number whose successor is Inf.
>*cough*bullshit writing the interval 1..infinity is very common
It is indeed very common to use the term "infinity" in mathematics. It is
also very common to use the term "false" in mathematics. That does not
mean that infinity is a number (and by "number" I explicitly mean any
discrete member of one of the more commonly used infinite sets like
"natural numbers", "rational numbers", "real numbers", "complex numbers",
etc) any more than it means that false is a number. I'm not saying that
"infinity" and now also "false" are not useful notions, nor that they're
somehow unmathematical; I'm saying they're not numbers, and that
consequently it is meaningless to apply operations defined only upon
numbers upon them. When you say something like N = 1..infinity, because,
for example, you are describing an infinite sum, you are writing shorthand
for a rather more complicated notion. It is *not* the same as what occurs
when you write N = 1 .. 10, even though it is nearly identical in
appearance. N=1..10 means starting out with N set to the number 1 and then
repeatedly incrementing it by one until you have reached the number 10, at
which point you stop because you have reached the endpoint. However, when
you write N=1..infinity, and now lexically substitute in my previous
sentence "infinity" wherever "10" appeared, you will see that the resulting
sentence makes rather less sense than the original, even though lexically
both N=1..10 and N=1..infinity are rather similar to each another. What
they actually mean, however, is not. One of them ends, the other does not.
Both are useful and powerful and meaningful, but they are not the same kind
of thing.
--tom
