How do I append values in order to an existing list using only cons?

Question

In lisp I am trying to append values in order to a list using only the basic functions: setq cons car and cdr.

I can create the list backwards but I am having difficulty figuring out how to push them in order, how can this be done?

(setq list NIL)
(setq list (cons 1 list))
(setq list (cons 2 list))
(setq list (cons 3 list))

Result:
(3 2 1)

Answer 1

The usual idioms are either to use the :collect feature of an extended loop or to accumulate by pushing (as you described) and reverse in the end.

As an example, here are two versions of a simple range function that returns the integers from 0 below n:

(defun range (n)
  (loop :for i :below n
        :collect i))

(defun range (n)
  (let ((list ()))
    (dotimes (i n)
      (push i list))
    (reverse list)))

Under the restrictions you mentioned, I'd recommend implementing your own reverse and using it. Here is a tail recursive example, but note that tail recursion needs not be supported by your Lisp implementation.

(defun own-reverse (list &optional (acc ()))
  (if (endp list)
      acc
      (own-reverse (rest list)
                   (cons (first list) acc))))

Answer 2

Lisp lists are singly linked lists. Really, there's no "list" as such, just a bunch of cons-cells, also called pairs, that we interpret as a list by convention. (cons x y) produces a pair (x . y). As a special case, when the cdr of a cons is a list, e.g., in (x . (1 2 3)) we write the pair as (x 1 2 3). And the symbol nil is the empty list, so (x . nil) is (x). So, with cons, all you can do is create a new pair. If you have an existing list, l = (a b c…), and a new element, e, you could create the list (e a b c…), which you've already done, or you can create the new list ((a b c…) e), which isn't really what you want.

To modify the tail of the list, you need to be able to update the cdr of an existing cons cell. E.g., if you have (a b c), which, in the non shorthand form, is (a . (b . (c . nil))), you could do:

(setf (cdr (cdr (cdr the-list))) (list 'd))

and you'd replace the nil with (d), to get (a b c d). That requires using setf, rather than setq, since setq can only modify variables, not arbitrary places (like the cdr of a cons cell).

Idiomatically, if you're getting items in the reverse order that you need them, it's a common idiom to create the list in reverse, just like you're doing (or using push, etc.), and then to reverse it at the end. E.g., here's what a one-list version of mapcar could look like:

(defun mapkar (function list)
  "A simple variant of MAPCAR that only takes one LIST argument."
  ;; On each iteration, pop an element off of LIST, call FUNCTION with
  ;; it, and PUSH the result onto the RESULTS list.  Then,
  ;; destructively reverse the RESULTS list (it's OK to destructively
  ;; modify it, since the structure was created here), and return it.
  (let ((results '()))
    (dolist (x list (nreverse results))
      (push (funcall function x) results)))

Here's a tail recursive version of the same thing:

(defun mapkar (function list &optional (result '()))
  (if (endp list)
      (nreverse result)
      (mapkar function
              (rest list)
              (cons (funcall function (first list))
                    result))))

Answer 3

This is an surprising broad topic. First of, normally, you don't append single items to a list. The usual way of handling situations like the one you're probably in is by first collecting the wanted values into a list, and then reversing that list to get the order right:

(let ((my-list '()))
  (dotimes (i 10)
    (setf my-list (cons i my-list)))
  (nreverse my-list)) ; NOTE: nreverse destructively modifies its argument
;;=> (0 1 2 3 4 5 6 7 8 9)

Of course you can write yourself an function to "append" a value to a list, returning a new one:

(defun my-append (value list)
  (if (null list)
      (cons value '()) ; or use (list value)
      (cons (first list) (my-append value (rest list)))))

You can transform this to a tail recursive variant, but that won't solve the main issue of this function: It needs to traverse the whole list for each element to append it. Thus, this is in O(n) with n being the length of the list.

Another issue is that this function is consing a lot, that is it is generating a lot of additional cons cells, causing a lot of work for the memory management. One could solve that by making it destructively modifying its argument, though.

See also the function append that is already part of Common Lisp.

To give you an overview, you can either

• collect the values in the "wrong" order (using cons) and then destructively reverse that list (nreverse)
• collect the values in the "wrong" order and then create a new, reversed list with the values in the right order (reverse)
• actually append your values to the list, tolerating possible quadratic or worse run time.
• actually append your values to the list, destructively modifying the lists structure (nconc). This is an improvement against append because you don't need to allocate lots of new cons cells, but you still have the run time issue.

---

Based on uselpa's "hack" I wrote functions to operate with such a "list". It consists of a cons, whose car points to the beginning of the list (i.e. the list), and whose cdr points to the last cons cell of the list. Though that last cell is always (nil . nil), simplifying appending a value:

First, one sets the car of that last cell to the new value, then sets the cdr to a new cell (nil . nil), and finally returns that new "list":

(defun empty-al ()
  (let ((cell (cons nil nil)))
    (cons cell cell)))
(defun cons-al (value al)
  (cons (cons value (car al))
        (cdr al)))
(defun append-al (value al)
  (let ((new-cell (cons nil nil)))
    (setf (cadr al) value
          (cddr al) new-cell)
    (cons (car al) new-cell)))

Answer 4

There's a technique (I don't remember if it has a specific name) which consists in creating an initial cons cell with any car value and keeping a pointer to the cdr. Appending then consists of setfing the pointer's cdr and advancing the pointer. The list you want will at any time be the cdr of the initial cons cell:

? (progn (setq lst (cons 'head nil)) (setq lst-p lst) (cdr lst))
NIL
? (progn (setf (cdr lst-p) (cons 1 nil)) (setq lst-p (cdr lst-p)) (cdr lst))
(1)
? (progn (setf (cdr lst-p) (cons 2 nil)) (setq lst-p (cdr lst-p)) (cdr lst))
(1 2)
? (progn (setf (cdr lst-p) (cons 3 nil)) (setq lst-p (cdr lst-p)) (cdr lst))
(1 2 3)

So this only uses setq, cons, cdr but also setf.