Re: replacing a certain element in a list with another

[Roland Winkler <Roland.Winkler@physik.uni-erlangen.de>]

Barry Margolin <barry.margolin@level3.com> writes:

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

Thank you very much!

It might be helpful to add a comment to the docstring or info page
for nreverse saying that its argument is modified such that
afterwards it is a 1-element list containing the last element of the
reversed list.

Roland