Olin Shivers <xxxxxx@mongkok.ai.mit.edu> writes:

 >    From: Doug Currie <xxxxxx@flavors.com> 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.

Alternatively, the length of a list as the number of elements in the
list, in which case a circular list has a finite length.

It's also probably a lot more useful to have length return the number
of elements in a circular list than some special value indicating that
the list is circular.  If one's working with circular lists a lot I'd
expect that wanting to know the size of the different lists would be
more common than just wanting to know whether or not the lists are
circular.  Returning a special value for circular lists makes length
useless for circular lists - it degenerates to circular? on this
subclass of lists, which doesn't seem to be good design.

It's also more consistent with (a b . c) and (a b) having length 2.
If the last cdr points back to the head why should the length be
different than the (a b . c) case?

Finally, what about lists that aren't completely circular - ones whose
last cdr points into themselves?  Or were you thinking of these too
when you said "circular lists"?

So, I'm strongly in favor of a generalized length = number of
elements, not = number of possible cdrs.

However, I don't think a generalized length is such a good idea.  It
implies a substantial amount of additional overhead on computing the
length of a list.  This overhead remains no matter what you return for
circular lists - it's the act of detecting them which adds the
overhead.

To summarize, I'm in favor of a length fcn which goes into an infinite
loop on circular lists, but if you're going to include a generalized
length fcn I think the length of a circular list should be the number
of elements in the list, not any special value.

--
Harvey J. Stein
BFM Financial Research
xxxxxx@bfr.co.il