[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: LIST-LENGTH & circular lists
An 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:
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.
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
(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.
Cygnus Solutions bothner@xxxxxxxxxx http://www.cygnus.com/~bothner