ziggy@HX.LCS.MIT.EDU (12/05/89)
Are there any LISP implementations that attempt to make LENGTH of a list be a less than linear-time operation. I can imagine especially for immutable lists that this is easily achieved. Only SET-CDR! seems to be a fly in the ointment. ~Ziggy
cerys@BBN.COM (Dan Cerys) (12/05/89)
Are there any LISP implementations that attempt to make LENGTH of a list be a less than linear-time operation. I can imagine especially for immutable lists that this is easily achieved. Only SET-CDR! seems to be a fly in the ointment. The Zetalisps of old (probably still true of Explorers and Genera) used to provide an ART-Q-LIST array type. Such arrays were a cross between a general (ART-Q) array and a list. Application of the wonderfully mnemonic G-L-P function would return the "list" equivalent of the array. Preventing any flies from mucking about, SET-CDR! (RPLACD) on this "list" was an error. Because of these restrictions, it would seem that LENGTH of such "lists" would require constant time, regardless of length (just like determining LENGTH of an array). However, I don't know if this was the case. Dan