Re: LIST-LENGTH & circular lists

*Per Bothner*31 Mar 1999 06:05 UTCAn idea I had when I was working on abstract sequence operators: A cyclic list (or sequence if you want to be more general) has two parts: The non-repeated prefix, plus the repeated cyclic part. If you really want to work with cyclic lists, you want to know both lengths. Hence: (finite-length L) Returns the length of a proper list. For a cyclic list, returns the length of the initial non-repeated part. For a finite improper list, returns the number of pairs in the chain, including the final pair that has a non-list tail. (cycle-length L) Returns the number of pairs that are "repeated", before a cdr points back to the beginning of the repeated part. Returns 0 for a proper list. I'm not sure what it should return for an improper finite list: -1 lets is distinguish this case, 0 may work better. (finite-part L) == (take L (finite-length L)) (cycle-part L) == (take (drop L (finite-length L)) (cycle-length L)) The invariant for any list L (proper or cyclic, at least) is that L is equal to (finite-part L) followed by an infinite number of copies of (cycle-part L). Unfortunately, I don't know any efficient algorithm for calculating finite-length and cycle-length, but perhaps someone is more clever. --Per Bothner Cygnus Solutions xxxxxx@cygnus.com http://www.cygnus.com/~bothner