[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:

(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     bothner@xxxxxxxxxx     http://www.cygnus.com/~bothner