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

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)
        (tortoise-advance #t)
        (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-advance (not tortoise-advance))
      (if tortoise-advance
           (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))