Re: To be a list or not

[Bob Rogers]

   From: "Stephen J. Turnbull" <address@hidden>
   Date: Sun, 30 Dec 2007 09:54:41 +0900

   Tom Tromey writes:
    > >>>>> "Stephen" == Stephen J Turnbull <address@hidden> writes:
    > 
    > Stephen> But please call it `true-list-p', which is the name of the
    > Stephen> similar XEmacs built-in.
    > 
    > Here's one stab at it.  This is basically lifted from safe-length.

   Looks very familiar.

   XEmacs implements one change you might think about.  Specifically, it
   delays starting the tortoise until the length is "long enough to
   suspect circularity".  I don't know if the value chosen was tuned or
   not.  As I understand it, this makes the function slightly faster for
   shorter lists, slightly slows down longer true lists, and might double
   the detection time for cyclical lists.

   Looks like a win to me, but YMMV.

Another trick is to unroll the loop so that it follows the tortoise, as
done in the CMU Common Lisp list-length function shown below (which is
in the public domain).  If you combine both tricks, you would have two
loops, the first of which only needs to maintain a tail and a counter,
and the second only needs to maintain a tail and a tortoise.

   But it's not at all clear that this is worth all that trouble . . .

                                        -- Bob

------------------------------------------------------------------------
(defun list-length (list)
  "Returns the length of the given List, or Nil if the List is circular."
  (do ((n 0 (+ n 2))
       (y list (cddr y))
       (z list (cdr z)))
      (())
    (declare (fixnum n) (list y z))
    (when (endp y) (return n))
    (when (endp (cdr y)) (return (+ n 1)))
    (when (and (eq y z) (> n 0)) (return nil))))