Append

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

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:

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, 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:

append :: [a] -> [a] -> [a] append xs ys = foldr (:) ys xsThis 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?
Synonyms:

Look at other dictionaries:

  • append — ap‧pend [əˈpend] verb [transitive] to attach or add something to a piece of writing: • I have appended a letter which you sent to us last year. append something to something • The director has the right to append comments to the final report. * * …   Financial and business terms

  • Append — Ap*pend ([a^]p*p[e^]nd ), v. t. [imp. & p. p. {Appended}; p. pr. & vb. n. {Appending}.] [L. appendere or F. appendre: cf. OE. appenden, apenden, to belong, OF. apendre, F. appendre, fr. L. append[=e]re, v. i., to hang to, append[e^]re, v. t., to… …   The Collaborative International Dictionary of English

  • append — I verb add, addere, adiungere, affix, annex, attach, augment, conjoin, connect, extend, fasten include, insert, join, subjoin, supplement II index affix, annex (add) …   Law dictionary

  • append — (v.) late 14c., to belong to as a possession or right, from O.Fr. apendre (13c.) belong, be dependent (on); attach (oneself) to; hang, hang up, and directly from L. appendere to cause to hang (from something), weigh, from ad to (see AD (Cf. ad )) …   Etymology dictionary

  • append — *add, subjoin, annex, superadd Analogous words: affix, attach, *fasten Contrasted words: *detach, disengage: curtail (see SHORTEN) …   New Dictionary of Synonyms

  • append — [v] add, join adjoin, affix, annex, attach, conjoin, fasten, fix, hang, subjoin, supplement, tack on*, tag on*; concepts 85,113,160 Ant. disjoin, subtract, take away …   New thesaurus

  • append — ► VERB ▪ add to the end of a document or piece of writing. ORIGIN Latin appendere hang on …   English terms dictionary

  • append — [ə pend′] vt. [ME appenden < OFr apendre < L appendere < ad , to + pendere, hang: see SPIN] to attach or affix; add as a supplement or appendix …   English World dictionary

  • append — v. (D; tr.) to append to (to append a translation to a document) * * * [ə pend] (D; tr.) to append to (to append a translation to a document) …   Combinatory dictionary

  • append — 01. The secretary [appended] a note at the end of the memo, asking people to verify reception. 02. Many people [append] a little quotation or joke to their e mail signature. 03. The director s name is [appended] to all official documents. 04.… …   Grammatical examples in English

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”