At 9:35 PM +0200 2/22/99, Harvey J. Stein wrote:
>[...]
>
>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"?

I consider these circular lists.

>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.

Not necessarily. The length function must compute a count. At some point
this count will exceed a (implementation dependent) limit, e.g., the size
of the heap, when it becomes clear that the list is circular. For
non-circular lists this adds little overhead, just one integer compare per
iteration (in a clever low level implementation, it may add no overhead if
it's combined with the detection of fixnum overflow to switch to bignum
addition). For circular lists, this may take a while to detect, but on
today's fast processors with lists that fit in cache it can be quite
competitive with more complex approaches that allocate memory or use N*N*N
algorithms. Using these counting techniques a list-length can be provided
competitive in performance with a non-circular-list-detecting version.
However, this approach doesn't provide a result for circular list more
useful than 0 or #f.

e