Email list hosting service & mailing list manager


Re: LIST-LENGTH & circular lists Andrew Pochinsky 23 Apr 2001 16:00 UTC

Olin,
  There is actually a difference between 3-element cicrular list

   (define three-element (1 7 2 1 7 2 ...))

and a similary looking 6-element circular list

   (define six-element (1 7 2 1 7 2 ...))

E.g.,
   (eq? three-elements (cdddr three-elements)) ==> #t
   (eq? six-elements (cdddr six-elements)) ==> #f

unless, of course, one considers those pesky eq?'s side-effect....

--andrew

   Date: Mon, 23 Apr 2001 11:40:28 -0400
   From: xxxxxx@cc.gatech.edu

   Noah-

   After some reflection back when all this discussion happened the first time
   around, I came to the conclusion that this whole notion of "number of elts"
   was not a good one.

   See, what is the difference between a "3-element" circular list
       (1 7 2 1 7 2 ...)
   and a "six element" circular list
       (1 7 2 1 7 2 ...)
   The difference comes when you start side-effecting the list or its elements.
   Barring side-effects, *you can't observe any differences*. So they are the
   same list, if you live in a pure-functional world.

   I'm not opposed to some sort of lower-level utility that exposes the
   underlying structure of the list, but we should keep the levels clear.
   So you would want to give such a utility a distinct name, like
       (circular-list-number-of-elements l) -> integer
   or
       (circular-list-number-of-pairs l) -> integer
   Note that I avoided the term "length" in the name.

   I also think it's probably not so useful as to warrant inclusion in a
   general list library.
       -Olin