How does "Cons" work in Lisp?

lisp common-lisp cons
Amir Jalilifard picture Amir Jalilifard · Apr 17, 2015 · Viewed 8.2k times · Source

I was studying Lisp and I am not experienced in Lisp programming. In a part of my studies I encountered the below examples:

> (cons ‘a ‘(a b))  ----> (A A B)
> (cons ‘(a b) ‘a)  ----> ((A B).A)

I was wondering why when we have (cons ‘a ‘(a b)) the response is (A A B) and why when we change it a little and put the 'a after (a b), the response is a dotted list like ((A B).A)? What is the difference between the first code line and the second one? What is going on behind these codes?

Answer

csl picture csl · Apr 17, 2015

It's pretty easy to understand if you think of them as cons-cells.

In short, a cons cell consists of exactly two values. The normal notation for this is to use the dot, e.g.:

(cons 'a 'b) ==> (A . B)

But since lists are used so often in LISP, a better notation is to drop the dot. Lists are made by having the second element be a new cons cell, with the last ending a terminator (usually nil, or '() in Common Lisp). So these two are equal:

(cons 'a (cons 'b '())) ==> (A B)
(list 'a 'b) ==> (A B)

So (cons 'a 'b) creates a cell [a,b], and (list 'a 'b) will create [a, [b, nil]]. Notice the convention for encoding lists in cons cells: They terminate with an inner nil.

Now, if you cons 'a onto the last list, you create a new cons cell containing [[a, [b, nil]], a]. As this is not a "proper" list, i.e. it's not terminated with a nil, the way to write it out is to use the dot: (cons '(a b) 'a) ==> ((a b) . a).

If the dot wasn't printed, it would have to have been a list with the structure [[a, [b, nil]], [a, nil]].

Your example

When you do (cons 'a '(a b)) it will take the symbol 'a and the list '(a b) and put them in a new cons cell. So this will consist of [a, [a, [b, nil]]]. Since this naturally ends with an inner nil, it's written without dots.

As for (cons '(a b) 'a), now you'll get [[a, [b, nil]], a]. This does not terminate with an inner nil, and therefore the dot notation will be used.

Can we use cons to make the last example end with an inner nil? Yes, if we do

(cons '(a b) (cons 'a '())) ==> ((A B) A)

And, finally,

(list '(a b) 'a))

is equivalent to

(cons (cons (cons 'a (cons 'b '())) (cons 'a '())))

Related questions

What's the best way to learn LISP?

I have been programming in Python, PHP, Java and C for a couple or years now, and I just finished reading Hackers and Painters, so I would love to give LISP a try! I understand its totally diferent from what …

Read More
Check if item is in a list (Lisp)

What's a simple way to check if an item is in a list? Something like (in item list) might return true if item=1 and list=(5 9 1 2) and false if item=7

Read More
Lisp commenting convention

What is the Lisp convention about how many semicolons to use for different kinds of comments (and what the level of indentation for various numbers of semicolons should be)? Also, is there any convention about when to use semicolon comments …

Read More