# Lisp: Cons cell

I found that most of time, I do not need to understand “cons cell”. However, I gave up to my curiosity.

In Lisp, a singly-linked list is a chain of cons cells, that is terminated by nil. However, cons cell can be used as just ordered pairs, binary trees, etc. [1]

“cons cell is 2-vector of pointers” [2]

An ordered pair of strings, like in figure 1, can be **cons**tructed by the command *(cons “donkey” “rabbit”)*. And we can access the first element by *(car the-cons-cell-in-figure1)*; and the second element by *(cdr a-cons-cell-in-figure1)*.

A list can be constructed by **cons** too. For example, (cons “cat” (cons “donkey” (cons “rabbit” nil))) is equivalent to (list “cat” “donkey” “rabbit”).

According to figure 2, *(car the-list-in-figure2)* is “cat”; and *(cdr the-list-in-figure2)* is (cons “donkey (cons “rabbit” nil)). Since (cons “donkey (cons “rabbit” nil)) is equivalent to (list “donkey” “rabbit”), *(cdr the-list-in-figure2)* is (list “donkey” “rabbit”).

Cons cells can be used for implementing an immutable binary search tree. [3] However I do not explain it here.

Similar thing to cons in other languages can be done too. For example, in Python, we can use tuples, *(“cat”, (“donkey”, (“rabbit”, None)))*, which is quite similar to *(cons “cat” (cons “donkey” (cons “rabbit” nil)))*. A recursive function for counting elements can be written like below:

which is quite similar to

I tried *count((“cat”, (“donkey”, (“rabbit”, None)))) and it just worked. However, most of time, there is no convenient command like (list …) *out-of-the-box. And len(None) in Python does not equal to zero.

In brief, cons cell can be viewed as an array that are exactly 2 elements. Cons cells are used in constructing singly-linked list and other data structures. Especially for a singly-linked list, Lisp has been designed to use cons cell conveniently.