Lists and Member Implementation in Common Lisp

Question

I'm just starting to learn Common Lisp and the text I'm reading uses an example with the member function.

I'm unsure of the distinction between these two blocks of code:

(if (member nil '(1 nil 2 3))
    'contains-nil
    'does-not-contain-nil)

returns CONTAINS_NIL

(if (member nil '(1 2 3))
    'contains-nil
    'does-not-contain-nil)

returns DOES-NOT-CONTAIN-NIL

From what I understand, lists are equivalent to nested cons cells, so I would think (member nil (cons 1 (cons 2 (cons 3 nil))) would return (nil), but it just returns nil. I'm not sure how a compiler or interpreter would make that distinction, and if someone could give me some insight on how I could implement the member function, I'd appreciate it.

Answer 1

A cons cell holds two values, typically called its car and its cdr. The expression (cons x y) returns a cons cell whose car is x, and whose cdr is y. In Lisp, a list is either the empty list (typically the symbol nil), or a cons cell. When a list is a cons cell, the first element of the list is the cons cell's car, and the rest of the list is the cons cell's cdr. Consider the list (1 2 3). It is a cons cell, and the first element of the list is 1. The rest of the list is not empty, so it must be another list whose first element is 2. The rest of that list is not empty, so it must be another list whose first element is 3. The rest of that list is empty, i.e., nil. Based on that analysis, we can see why the list is formed by

(cons 1 (cons 2 (cons 3 nil)))
== (1 2 3)

In a chain of cons cells that make up a list, the elements of the list are the car values of each cons cell in the chain. Lists can be elements of lists, as in

(cons 1 (cons nil (cons 2 (cons 3 nil))))
== (1 nil 2 3)

or

(cons 1 (cons (cons 2 (cons 3 nil)) nil))
== (1 (2 3))

but just because we see nil in the longer expression doesn't mean that nil is an element of the list.

Answer 2

MEMBER looks only at the elements of the list, not the list itself. An empty list is something different than an empty list with another empty list as an element.

() is not the same as (()). () is not the same as (nil).

Since a list is made of cons cells, the elements are the cars of the cons cells.

Answer 3

A list is defined to be either the empty list NIL or to be a cons cell whose CAR is an element of the list and whose CDR is another list. The list that is produced by

(cons 1 nil)

is a list that has the element 1 and also all the elements of the empty list. The empty list has no elements, so NIL is not an element of the list. It is similar with sets: Although the empty set is a subset of any set it is not an element of every set (while it isn't generally prohibited from being an element of a set).

One way o implement MEMBER is like this:

(defun member (item list)
  (if list
      (if (eql item (car list))
          list
          (member item (cdr list)))))

So if LIST is NIL the whole function will return NIL.

Answer 4

Our own version of the predefined member function in lisp can be defined as :

(defun member2 (item lst)
  (if lst
      (if (eql item (car lst))
          T
          (member2 item (cdr lst)))))