An Example Common Lisp Function Definition

Consider the binary trees x and y below.

In Lisp, x is written as the list '(A B) or, equivalently, as '(A B . NIL). Similarly, y may be written '(C D E). Suppose we wish to replace the right-most tip of x by the entire tree y. This is denoted (app x y), where app stands for ``append''.

We can define app with:

(defun app (x y)                           ; Concatenate x and y.
  (declare (type (satisfies true-listp) x)); We expect x to end in NIL.
  (cond ((endp x) y)                       ; If x is empty, return y.
        (t (cons (car x)                   ; Else, copy first node
                 (app (cdr x) y)))))       ;  and recur into next.

If you defined this function in some Common Lisp, then to run app on the x and y above you could then type

(app '(A B) '(C D E))
and Common Lisp will print the result (A B C D E).