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

Re: LIST-LENGTH & circular lists



   Date: Mon, 23 Apr 2001 12:00:06 -0400 (EDT)
   From: Andrew Pochinsky <avp@xxxxxxxxxxxxx>

   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....

Exactly. The whole notion of EQ? is tied up with the notion of side-effects.
For example, if I tell you that two pairs P1 & P2 are EQ?, that means that 
if you SET-CAR! P1, P2 will change.

If I don't allow side-effects to list cells (as in ML), then you can't
tell the difference between two cons cells with identical cars & cdrs.

So, there are basically these two levels: pure lists and side-effectable lists.
In the pure-list world, it is not interesting or even well-defined to ask
the how-many-elements-in-this-circular-list question. In the side-effectable
list world, it makes sense.
    -Olin