why the change is in place for the list with elisp?

Question

I have a question about elisp. For example:

(setq trees '(maple oak pine birch))
      -> (maple oak pine birch)
(setcdr (nthcdr 2 trees) nil)
      -> nil
trees
      -> (maple oak pine)

I thought (nthcdr 2 trees) returns a new list - (pine birch) and put the list into the setcdr expression, which should not change the value of trees. Could anyone explain it to me?

Answer 1

If you read the documentation string for nthcdr, you'll see that it just returns a pointer to the "nth" "cdr" - which is a pointer into the original list. So you're modifying the original list.

Doc string:

Take cdr N times on LIST, return the result.

Edit Wow, "pointer" seems to stir up confusion. Yes, Lisp has pointers.

Just look at the box diagrams used to explain list structure in lisp (here's Emacs's documentation on that very thing):

     --- ---      --- ---      --- ---
    |   |   |--> |   |   |--> |   |   |--> nil
     --- ---      --- ---      --- ---
      |            |            |
      |            |            |
       --> rose     --> violet   --> buttercup

Look at all those arrows, they almost look like they're .... pointing to things. When you take the cdr of a list, you get what the 2nd box refers to (aka "points" to), be it an atom, a string, or another cons cell. Heck, check it out on Wikipedia's entry for CAR and CDR.

If it feels better to call it a reference, use that terminology.

cdr certainly does NOT return a copy of what it refers to, which is what was confusing RNAer.

Answer 2

R: "Look, in the sky! The Lambda Signal! A citizen is in trouble Lambda Man!"

LM: "I see it! And I've got just the box art they need."

---

In Lisps, lists are singly-linked data structures, comprised of elements called cons cells. Each of these cells is a structure that consists of

1. a pointer to a value
2. a pointer to the next cell

These are called the car and cdr respectively for historical reasons. Here's the traditional box art representing a 3-element list:

Structure:    (car . cdr -)--->(car . cdr -)--->(car . cdr)
                |                |                |      |
                v                v                v      v
Values:         1                2                3     nil

The car and cdr functions allow you to work with lists from this low level of abstraction, and return the values of the respective cells. Thus, car returns the 'value' of the cell, and cdr dereferences to the remainder of the list. nthcdr is a generalisation on top of cdr for convenience.

The value returned by cdr is a reference to a raw data structure, which is mutable at this level. If you change the value of a cons-cell's cdr, you are changing the underlying structure of the list.

Given:

 let A = '(1 2)    ~= (1 . -)-->(2 . nil)

 let B = '(3 4)    ~= (3 . -)-->(4 . nil)

Setting the cdr of (cdr A) to B will destructively concatenate A and B such that A is now the structure below:

 A                   B     
 (1 . -)-->(2 . -)-->(3 . -)-->(4 . nil)

As we've shown, a nil value in a cell's cdr represents the end of the list - there's nothing more that can be traversed. If we set the cdr of A to nil, we lobotomise the list, such that A is now

A                  
(1 . nil)  <- [Not pointing to anything - the rest of the list shall go wanting]

This is pretty much what you've done - you've mutated the underlying data structures using low-level functions. :) By setting one of the cell's cdrs to nil, you've trimmed the end off your list.

Answer 3

This is called 'mutation'. And is present everywhere apart from Haskell.

There are functions that mutate the data structures and functions that duplicate it.