[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: srfi-1@xxxxxxxxxxxxxxxxx*Subject*: Re: LIST-LENGTH & circular lists*From*: Per Bothner <bothner@xxxxxxxxxx>*Date*: Tue, 30 Mar 1999 22:05:58 -0800

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

- Prev by Date:
**Re: SRFI-1 round 2 discussion** - Next by Date:
**SRFI-1 round 3 discussion** - Previous by thread:
**The type-name prefix convention and LIST-...** - Next by thread:
**'everything is a list' as a separate issue** - Index(es):