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