APPEND

In computer programming, append is the name of a procedure for concatenating (linked) lists or arrays in some high-level programming languages.

Lisp

Append originates in the Lisp programming language. The append procedure takes two or more (linked) lists as arguments, and returns the concatenation of these lists.

(append '(1 2 3) '(a b) '() '(6))
;Output: (1 2 3 a b 6)

Since the append procedure must completely copy all of its arguments except the last, both its time and space complexity are O(n) for a list of n elements. It may thus be a source of inefficiency if used injudiciously in code.

The nconc procedure (called append! in Scheme) performs the same function as append, but destructively: it alters the cdr of each argument (save the last), pointing it to the next list.

Implementation

Append can easily be defined recursively in terms of cons. The following is a simple implementation in Scheme, for two arguments only:

(define (append l1 l2)
  (if (null? l1)
    l2
    (cons (car l1) (append (cdr l1) l2))))

Other languages

Following Lisp, other high-level languages which feature linked lists as primitive data structures have adopted an append. Other languages use the + or ++ symbols for nondestructive string/list/array concatenation.

Prolog

The logic programming language Prolog features a built-in append predicate, which can be implemented as follows:

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :-
    append(Xs,Ys,Zs).

This predicate can be used for appending, but also for picking lists apart. Calling

?- append(L,R,[1,2,3]).

yields the solutions:

L = [], R = [1, 2, 3] ;
L = [1], R = [2, 3] ;
L = [1, 2], R = [3] ;
L = [1, 2, 3], R = []

References

Steele, Guy L. Jr. Common Lisp: The Language, Second Edition. 1990. pg. 418, description of append.