[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: LIST-LENGTH & circular lists



   From: Doug Currie <e@xxxxxxxxxxx>
   If we accept Olin's proposition that "Everything is a list (Or: When you've
   got a hammer...)" then everything should have a list length. So, I ammend
   my suggestion above to say: Extend list-length so it terminates on
   circular-lists, returning 0 for anything which is a circular-list (isn't a
   proper-list or a dotted-list).

The first half strikes me as a sensible proposal: extend LENGTH so it is
required to terminate on every possible Scheme value.

But defining the length of an infinite list to be 0 is not such a good idea, I
think. The length of () is 0. The length of "foo" is 0. The length of a
circular list ain't 0! It's infinite. The notion of "length" is connected to
the number of times you can apply CDR to the value, which is 0 times for ()
and unbounded for a circular list. So you need some kind of infinity
marker/value. (If this were J, we'd just have it return infinity.)  We could
draft #F to serve as the infinity value, which has the charm of being easy to
detect using conditionals like AND, OR and COND's => clause.

On the other hand, this does mean that you now have to remember and test for
the anomalous non-integer case when you use LENGTH. This is a definite warning
flag for me. Forget to make the test, and you could have a bogus false value
pop up in your system, get passed around, and surface 30 minutes later way far
away in some other distant arithmetic calculation and blow up your program. So
some programmers might *prefer* to have LENGTH just go into an infinite loop,
which would pinpoint the problem right where it occurred, or (better still)
get your attention by detecting the error and reporting it, again pinpointing
the problem. Thus they could always assume when writing code that if LENGTH
returns at all, it will definitely produce an integer.

So, it also seems to me to be just as reasonable to require LENGTH to
produce a result on all Scheme values *of finite length*. Values not having
finite length could either cause LENGTH to report an out-of-domain error or we
could simply not define what the function does.

These two modes of use are why I have suggested we provide both
    (LENGTH x)	-> integer		(or diverge or report an error)
    (LENGTH+ x) -> integer or #f
This way, if you are prepared to deal with a possible non-integer value,
you can consciously write down a call to the extra-special LENGTH+ function.
Otherwise, you'll never see a non-integer.

I note that I previously called these things LIST-LENGTH and LIST-LENGTH+, but
that was a brain-o. The R5RS name is LENGTH, not LIST-LENGTH. It is a general
fact of list-lib's design that I have pervasively dropped the type-prefix
LIST- from all procedures, just as the RnRS's have. The LIST-LENGTH crept
in because Currie used it in the msg that raised this whole topic, and I
responded to that, and we were off and running. Let's return to the RnRS
name roots for now.
    -Olin