Append
4334924
216590337
2008-06-02T09:41:15Z
Ghettoblaster
6603820
[[WP:UNDO|Undid]] revision 216552933 by [[Special:Contributions/24.217.195.120|24.217.195.120]] ([[User talk:24.217.195.120|talk]])
{{context}}
In [[computer programming]], '''<code>append</code>''' is the name of a [[procedure]] for concatenating ([[linked list|linked]]) lists or [[array]]s in some [[high-level programming language]]s.
===Lisp===
<code>Append</code> originates in the [[Lisp programming language]]. The <code>append</code> procedure takes two or more [[linked list|(linked) list]]s 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 <code>append</code> procedure must completely copy all of its arguments except the last, both its [[Computational complexity theory|time and space complexity]] are [[Big O notation|O(''n'')]] for a list of <math>n</math> elements. It may thus be a source of inefficiency if used injudiciously in code.
The <code>nconc</code> procedure (called <code>append!</code> in [[Scheme (programming language)|Scheme]]) performs the same function as <code>append</code>, but [[in-place algorithm|destructively]]: it alters the [[Car and cdr|cdr]] of each argument (save the last), pointing it to the next list.
====Implementation====
<code>Append</code> can easily be defined [[recursion|recursively]] in terms of <code>[[cons]]</code>. The following is a simple implementation in Scheme, for two arguments only:
(define append
(lambda (ls1 ls2)
(if (null? ls1)
ls2
(cons (car ls1) (append (cdr ls1) ls2)))))
===Other languages===
Following Lisp, other [[high-level language]]s which feature [[linked list]]s as primitive [[data structure]]s have adopted an <code>append</code>. Other languages use the + or ++ symbols for nondestructive [[string (computer science)|string]]/list/array concatenation.
====Prolog====
The [[logic programming language]] [[Prolog programming language|Prolog]] features a built-in <code>append</code> 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 = []
====Miranda====
This right-[[Fold (higher-order function)|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 (higher-order function)|fold]], and [[cons|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 (higher-order function)|fold]] has the same effect as the Scheme implementation above, for three arguments.
append3 :: [a] -> [a] -> [a] -> [ [a] ]
append3 xs ys zs = foldr (:) [] [xs, ys, zs]
We may extend this to any number of arguments by adding parameters and expanding the [[Type signature|type signature]].
== 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. <i>Computer Journal 32</i>, 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 <code>append</code>.
[[Category:Functional programming]]
[[Category:Lisp programming language]]
[[Category:Programming constructs]]
[[Category:Articles with example code]]