Re: replacing a certain element in a list with another

[Barry Margolin]

In article <m3k76xf34y.fsf@tfkp07.physik.uni-erlangen.de>,
Roland Winkler  <Roland.Winkler@physik.uni-erlangen.de> wrote:
>Kai Grossjohann <kai.grossjohann@gmx.net> writes:
>> Well, (nreverse x) does destructively modify the list x, but
>> afterwards the value if x is not what you think:
>> 
>> *** Welcome to IELM ***  Type (describe-mode) for help.
>> ELISP> (setq x (list 1 2 3 4))
>> (1 2 3 4)
>> 
>> ELISP> (nreverse x)
>> (4 3 2 1)
>> 
>> ELISP> x
>> (1)
>> 
>> ELISP> 
>> 
>> Clear?
>
>...not really  :-)
>
>I tried to understand the docstring and the info page. However, I
>could not really make use of it. So what is it that nreverse is
>doing with its argument? And when is this useful??

When you start, you have the following:

Cell A: car = 1
        cdr = reference to Cell B
Cell B: car = 2
        cdr = reference to Cell C
Cell C: car = 3
        cdr = reference to Cell D
Cell D: car = 4
        cdr = nil
x's value cell = reference to Cell A

When you call nreverse, it is passed the contents of x's value cell,
i.e. the reference to Cell A.  It reverses the list by keeping all the
car's the same, but reversing the cdr links; this changes things to:

Cell A: car = 1
        cdr = nil
Cell B: car = 2
        cdr = reference to Cell A
Cell C: car = 3
        cdr = reference to Cell B
Cell D: car = 4
        cdr = reference to Cell C

Now the first cons in the reversed list is Cell D, and nreverse returns
this as its value.

But x's value cell still contains a reference to Cell A, which has become
the last cons in the chain.  So when you print it, you just see the
1-element list containing the last element of the reversed list.

Why is it done this way?  Because this is the simplest way to reverse a
list in place.  It can just step through the list, replacing each cdr with
a reference to the preceding cons cell.  This is much easier than swapping
all the car's in order to keep the order of the conses intact.

-- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.