追加

Append — Grokipedia Fact-checked by Grok 3 months ago Append Ara Eve Leo Sal 1x In computer programming, append is an operation that concatenates two or more lists or arrays by adding the elements of one to the end of another, often used in high-level languages for manipulating dynamic data structures. Originating in the Lisp programming language in the late 1950s, it enables efficient handling of sequences without modifying the original structures in functional paradigms. Append is fundamental in algorithms, file operations, and database management, with implementations varying across languages like Prolog, Haskell, and Python. Definition and Purpose Core Operation The append operation serves as a core construct in computer science for concatenating two or more sequence s—such as lists or arrays—into a single new sequence that preserves the relative order of elements from each input. Specifically, it combines the sequences end-to-end, placing all elements from the first sequence before those from the second, and extending this pattern for any additional sequences involved. This results in a unified structure where the original ordering within each sequence remains intact, making append a key tool for sequence composition without altering the inputs. [1] [2] The semantics of the append operation can be illustrated through simple pseudocode , which emphasizes creating a new sequence by sequentially incorporating elements from the inputs: function append(seq1, seq2): result = empty_[sequence](/page/Sequence)() for each element in seq1: result.add(element) for each element in seq2: result.add(element) return result In this formulation, the operation iterates over the elements of the first sequence followed by the second, ensuring the output reflects their concatenated order; extensions to more than two sequence s follow the same iterative principle. [2] [3] Unlike related operations such as insertion—which places elements at arbitrary positions within a sequence —or prepending—which attaches elements to the beginning, append exclusively adds to the end, thereby maintaining a linear extension of the structure. [4] [1] This end-focused behavior distinguishes it in sequence manipulation, where it facilitates tasks like building accumulators through successive concatenations or merging disparate data streams into cohesive outputs. Linked lists commonly employ append for efficient tail-to-head linking in such scenarios. [2] [5] Applications in Data Structures In linked lists, the append operation for concatenating two lists typically involves traversing the first list to locate its tail node and then linking that tail 's next pointer to the head of the second list, achieving O(n time complexity where n is the length of the first list, without requiring additional space beyond the existing nodes. [6] For arrays , the append behavior differs significantly between fixed-size and dynamic variants. In fixed-size arrays , appending an element beyond the allocated capacity necessitates creating a new array of larger size , copying all existing elements into it, and then adding the new element, resulting in O(n time for each such operation where n is the current size . [7] Dynamic arrays , however, mitigate this through resizing strategies like doubling the capacity when full, which involves copying elements to the new array but yields an amortized O(1) time per append across a sequence of operations, as the total cost for m appends remains O(m). [8] [9] String append operations also vary based on mutability. For immutable strings, concatenation creates a new string object containing the combined contents, copying both original strings, which can lead to O(n²) time for repeated appends in a loop due to successive allocations. [10] Mutable string buffers, such as those implemented via resizable character arrays, allow in-place addition by extending the buffer as needed, similar to dynamic arrays, enabling efficient O(1) amortized appends without full recopying on each operation. [10] Append operations find practical use in algorithms for building result structures, such as in the merge step of merge sort where elements from two sorted sublists are sequentially appended to a new list based on comparisons, ensuring the final sorted output in O(n) time for the merge. [11] In logging systems, append facilitates extending files or buffers by adding new records to the end, often using mutable structures to maintain sequential integrity and support atomic writes for reliability. [12] Historical Development Introduction in Lisp The append function was developed in 1958 by John McCarthy as one of the foundational list-processing primitives in the Lisp programming language, designed to enable efficient manipulation of symbolic expressions central to early artificial intelligence research. [13] Lisp, short for LISt Processor, emerged from McCarthy's work at MIT to formalize recursive functions over symbolic data structures, where lists served as the primary representation for atoms and expressions. [14] As part of this system, append provided a means to concatenate lists, supporting the construction of complex symbolic forms without relying on low-level machine instructions. In Lisp , the syntax for append is (append list1 list2 ... ) , which takes one or more lists as arguments and returns a new list formed by copying the elements from all but the last input list and then attaching the last list, sharing its structure to avoid unnecessary duplication. [15] This behavior ensures the operation is non-destructive, preserving the original lists while producing a fresh result, which aligns with Lisp's emphasis on functional composition. The recursive definition underlying append— append[x; y] = [null[x] → y; T → cons[car[x]; append[cdr[x]; y]]] —reflects the language's theoretical roots in lambda calculus and recursive function theory. [15] The design rationale for append centered on facilitating symbolic computation and recursive algorithms in a functional style, allowing programmers to build and transform lists for tasks like expression evaluation and pattern matching without mutating data in place. [14] This non-mutating approach was crucial for debugging and reasoning about programs in AI contexts, where predictability in list operations prevented unintended side effects. Early documentation from the Lisp 1.5 system, released in 1962, illustrates append's usage in AI programs, such as merging lists in the Wang algorithm for automated theorem proving in propositional calculus, where it combined clause representations to explore logical inferences. [15] Its influence later extended to other programming languages, adapting list concatenation concepts beyond Lisp 's symbolic paradigm. Adoption Across Paradigms The append operation, originating in Lisp as a functional list concatenation tool, transitioned to logic programming paradigms in the 1970s, profoundly shaping Prolog 's approach to list manipulation. Prolog , pioneered by Alain Colmerauer and his team at the University of Marseille in 1972 , drew inspiration from Lisp's list structures to define predicates like append/3, which declaratively concatenates lists through unification and recursion . [16] This predicate, often exemplified in early Prolog systems for tasks such as member checks or reversal, enabled relational definitions without explicit control flow , marking a shift from Lisp's applicative-order evaluation to logic-based resolution. By the mid-1970s, append became a cornerstone of Prolog's list-processing capabilities, influencing implementations in systems like DEC-10 Prolog and facilitating applications in natural language processing and theorem proving. [17] In the 1980s, append concepts were integrated into subsequent pure functional languages, emphasizing immutability and non-strict evaluation to maintain referential transparency . Miranda, developed by David Turner starting in 1985, introduced the infix operator ++ for list concatenation , treating lists as polymorphic, lazy data structures that avoid side effects during composition. [18] This design choice aligned with Miranda's goal of higher-order functional programming , where ++ recursively builds new lists without modifying originals, supporting equational reasoning in programs. Haskell , formalized in 1990 by a committee including Turner, adopted the same ++ operator in its Prelude, standardizing append as a core function for pure expressions and enabling optimizations like fusion in list comprehensions. These integrations reinforced append's role in functional purity, distinguishing it from mutable variants by prioritizing composability over in-place updates. [19] During the 1990s, append adapted to imperative paradigms in languages like Perl and Python, where it manifested as methods for extending mutable arrays to support dynamic, side-effecting growth. Python's list.append() method, introduced in version 0.9.0 in 1991 by Guido van Rossum , adds elements in-place to resizable arrays using amortized constant-time over-allocation, catering to procedural scripting needs. Perl 's push function, present since the initial Perl 1.0 release in 1987 and refined in Perl 5 (1994), similarly appends values to the end of arrays, returning the new size and enabling stack-like operations in text processing tasks. [20] These adaptations prioritized efficiency for mutable structures, contrasting functional purity by allowing direct modification, though they retained conceptual ties to list extension for practical utility in systems programming . Key milestones in append's standardization included its formalization in the ANSI Common Lisp specification (INCITS 226-1994), which defined append as a non-destructive function copying all but the last list argument, ensuring consistent behavior across Lisp dialects for portable code. [21] This event solidified append's semantics in object-oriented extensions like CLOS. Additional