How to detect finite/infinite lists?

[Juanma Barranquero]

On Thu, 18 Sep 2003 12:28:41 -0700 (PDT), Brandon Michael Moore <brandon at its.caltech.edu> wrote:

> This is obviously equivalent to the halting problem so you
> can't really expect anything better in general.

No, obviously not in general. But a human wouldn't sweat to say that
[1..5] is finite and [1..] infinite. As I have no idea how the compiler
is implemented, I don't know if it knows whether what it has on its
hands is a fixed, short-length list (like [1..5], which I imagine the
compiler would perhaps pre-generate instead of lazy-evaluating it), or
one which in fact comes from some kind of generator function(s).

> Why do you need to test whether lists are infinite?

I had something like:

data Surreal = Surreal { leftSet::[Surreal], rightSet::[Surreal] }

where leftSet and rightSet could potentially contain infinite lists of
Surreals. Knowing that both sets are finite would allow to simplify some
numbers (in surreal numbers, it is the case that {-1|1} = {|}, for
example, and being able to simplify {-1|1} to {|} can help, specially
when trying to show/print the numbers).

> If your lists are being generated from finite
> descriptions maybe you could use a data structure that records the
> descriptions.

Yes, I think you're right.

> What do you want to use it for? If you are looking for strict alternation you
> should use this defintion.

Yes, strict alternation (output, in fact). I have lists of columns and
lists of separators and I interleave them while generating a line of
output.

Thanks,


                                                           /L/e/k/t/u