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.

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

Contents

[edit] 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.

[edit] 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
  (lambda (ls1 ls2)
    (if (null? ls1)
      ls2
      (cons (car ls1) (append (cdr ls1) ls2)))))

[edit] 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.

[edit] 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 = []

[edit] 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]

[edit] Haskell

This right-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.

[edit] 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.

[edit] References