# Re: LIST-LENGTH & circular lists

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.

```Sorry to be bringing up such an old subject, but I ran across this thread
as the result of a web search and couldn't help replying.

Before quoting the following, let me remind you that Harvey Stein proposed
that the "generalized length" of a list should be defined as the number of
elements, not the number of times you could apply cdr to the list.

On Feb 22 1999, Doug Currie wrote the following:
>At 9:35 PM +0200 2/22/99, Harvey J. Stein wrote:
>>...
>>However, I don't think a generalized length is such a good idea.  It
>>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
>
>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
>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.

I think you can compute the number of distinct elements in a circular list
in linear time and constant space without resorting to any
implemented-defined behavior of the runtime environment.

I defined the function below in MIT Scheme and evaluated the following:

(define l '(1 2 3 4 5 6 7))
(set-cdr! (list-tail l 6) (list-tail l 3))

(circular-list-length l)
;Value: 7

(circular-list-length '(1 2 3))
;Value: 3

(circular-list-length '())
;Value: 0

Here's the function definition, which works for non-circular lists as well.
```
```(define (circular-list-length lst)
"Return the number of distinct elements of circular list LST."
(let ((tortoise lst)
(hare lst)
(len 0))
;; Find a member of the list guaranteed to be within the cycle, and
;; compute length if list turns out to be non-circular.
(do ()
((null? hare))
(set! hare (cdr hare))
(set! len  (1+ len))
(set! tortoise (cdr tortoise)))
(if (eq? hare tortoise)
(begin
(set! hare '())
(set! len  0))))

(if (and (not (null? lst))
(zero? len))
(begin
;; Find period of cycle.
(set! hare (cdr tortoise))
(set! len 1)
(do ()
((eq? hare tortoise))
(set! hare (cdr hare))
(set! len (1+ len)))

;; Give hare a head start from the start of the list equal to the
;; loop size.  If both move at the same speed they must meet at
;; the nexus because they are in phase, i.e. when tortoise enters
;; the loop, hare must still be exactly one loop period
;; ahead--but that means it will be pointing at the same list
;; element.
(set! tortoise lst)
(set! hare (list-tail lst len))
(do ()
((eq? tortoise hare))
(set! hare (cdr hare))
(set! tortoise (cdr tortoise))
(set! len (1+ len)))))
len))
```