Append
From Wikipedia, the free encyclopedia
| The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style. (October 2009) |
In general, to append is to join or add on to the end of something. For example, an appendix is a section appended (added to the end) of a document.
In computer programming, append is the name of a procedure for concatenating (linked) lists or arrays in some high-level programming languages.
Contents |
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.<source lang="lisp">(append '(1 2 3) '(a b) '() '(6))
- Output
- (1 2 3 a b 6)
</source>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 
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:<source lang="scheme">(define append
(lambda (ls1 ls2) (if (null? ls1) ls2 (cons (car ls1) (append (cdr ls1) ls2)))))
</source>
Other languages
Following Lisp, other high-level languages which feature linked lists as primitive data structures have adopted an append Haskell uses the ++ operator to append lists. OCaml uses the @ operator to append lists.
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:<source lang="prolog">append([],Ys,Ys).append([X|Xs],Ys,[X|Zs]) :-
append(Xs,Ys,Zs).
</source>This predicate can be used for appending, but also for picking lists apart. Calling<source lang="prolog">
?- append(L,R,[1,2,3]).
</source>yields the solutions:
L = [], R = [1, 2, 3] ;L = [1], R = [2, 3] ;L = [1, 2], R = [3] ;L = [1, 2, 3], R = []
Miranda
This right-fold, from Hughes (1989:5-6), has the same semantics (by example) as the Scheme implementation above, for two arguments.
append a b = reduce cons b a
Where reduce is Miranda's name for fold, and cons constructs a list from two values or lists.
For example,
append [1,2] [3,4] = reduce cons [3,4] [1,2] = (reduce cons [3,4]) (cons 1 (cons 2 nil)) = cons 1 (cons 2 [3,4])) (replacing cons by cons and nil by [3,4]) = [1,2,3,4]
Haskell
This right-fold has the same effect as the Scheme implementation above:<source lang="haskell">append :: [a] -> [a] -> [a]append xs ys = foldr (:) ys xs</source>This is essentially a reimplementation of Haskell's ++ operator.
DOS command
append is a DOS command that allows programs to open data files in specified directories as if they were in the current directory. It appends the directories to the search path list.
References
- Hughes, John. 1989. Why functional programming matters. Computer Journal 32, 2, 98-107. http://www.math.chalmers.se/~rjmh/Papers/whyfp.pdf
- Steele, Guy L. Jr. Common Lisp: The Language, Second Edition. 1990. pg. 418, description of
append.