This page is part of the web mail archives of SRFI 1 from before July 7th, 2015. The new archives for SRFI 1 contain all messages, not just those from before July 7th, 2015.
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