The append function

I had explained my method to understand lisp code and the subst1 function in my previous post. In the following posts I explain three functions, append., pair. and assoc. This post will explain the append. function.

Once again, the steps I use to understand lisp code :

1. Construct a mental model by abstracting away all the details and consider the outermost structure.
2. Expand the next function in the program and create simple examples along the way.
3. See what actually happens to the simple examples created in the previous step by manually/mentally parsing the input.
4. Repeat steps 2) & 3).

The append. function

(append. x y) takes two lists and returns the result of concatenating x with y

    (defun append. (x y)
        (cond ((null. x) y)
              ('t (cons (car x) (append. (cdr x) y)))))

     ;; Definition of null.
    (defun null. (x)
        (eq x '()))

Skeletal code

    (defun append. (x y)
        (cond ((null. x) y)  ;; If x is nil return y
              ('t   (e2))))  ;; else return the value of e2
                  ;;  where e2 = (cons (car x) (append. (cdr x) y))

The base case is if x is nil then y is returned as it is without modification. For example,

    (append. () '(1 2 3))

Now, for the expression which is executed if x is not null.

    (cons (car x) (append. (cdr x) y))

As seen in the subst1 function in the previous post, append. too contains a recursive call to itself. It first strips off the first element of the list x. Since x is not null there will be such an element and the expression
(cdr x)
will return either the rest of the array or it will return the empty list.

The complete code for append. and a few examples

    (defun append. (x y)
        (cond ((null. x) y)
              ('t (cons (car x) (append. (cdr x) y)))))

    (defun null. (x)
        (eq x '()))

    ;; Examples

    (append. () '(1 (2 3) 4 5)) ;; the first list x is null

    (append. '(1) '(2 3))       ;; the first list, x, contains a single element

    (append. '(1 2) '(3 4 5))   ;; the first list, x, contains two elements

    (append. '(1 (2 3)) '(4 5)) ;; Again the first list, x, contains only two elements

One important thing to note is the manner in which a list is built up. For instance, let's have a look at what the list
'(1 2) consists of. It can be viewed as a series of cons as given below

(cons '1 (cons '2 ()))
    ==> (1 2)

;; Similarly,
(cons '3 (cons '1 (cons '2 ())))
    ==> (3 1 2)

;; And so forth ...

Now, let's run a few examples on the code and see how it is evaluated,

(append. '(1) '(2 3 4 5))

  (append. '(1) '(2 3 4 5))                     (append. '(1) '(2 3 4 5))
             |                                             |
             |                                             |
            cons                          ==>             cons              ==>  (cons '1 '(2 3)) 
           /    \                                        /    \
          /      \                                      /      \
   (car '(1))  (append. (cdr '(1)) '(2 3))             '1    (append. () '(2 3))

The pattern to be noticed is that the first list keeps getting shorter till it eventually becomes empty. Another example,

(append. '(2 1) '(3 4 5))

                    (append. '(2 1) '(3 4 5))  
                             |                   
                             |                   
                            cons                 
                           /    \                
                          /      \               
                   (car '(2 1))  (append. (cdr '(2 1)) '(2 3))   
                                            |
                                            |
                                 (append. '(1) '(2 3))

       But, we know what (append. '(1) '(2 3)) returns from the previous example.
       Thus,


                    (append. '(2 1) '(3 4 5))  
                             |                   
                             |                   
                            cons                 
                           /    \                
                          /      \               
                         '2    '(1 2 3)

      Which is (cons '2 '(1 2 3))   ==>   (2 1 2 3)