[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: LIST-LENGTH & circular lists
Olin Shivers <shivers@xxxxxxxxxxxxxxxxxx> writes:
> 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
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
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