Append and Concatenation

The append function

let rec append xs ys =
  match xs, ys with
  | [], ys -> ys
  | x :: xs, ys -> x :: append xs ys
(* val append : 'a list -> 'a list -> 'a list = <fun> *)

The pattern matches on a pair of lists. Two cases:

• If the first list is empty, return the second list unchanged
• Otherwise, cons the head of the first list onto the result of appending its tail to the second list

The infix operator @ is simply append:

let (@) = append

Evaluation trace

append [1; 2; 3] [4] => 1 :: append [2; 3] [4]
                      => 1 :: (2 :: append [3] [4])
                      => 1 :: (2 :: (3 :: append [] [4]))
                      => 1 :: (2 :: (3 :: [4]))
                      => [1; 2; 3; 4]

Complexity

Append scans its first argument and sets up a chain of cons operations:

• Time: O(n) where n is the length of the first argument
• Space: O(n) — each element of the first list is copied into a new cons cell
• Costs are independent of the second argument’s length

The string of pending cons operations means this function is not iterative. Adding an accumulator could make it iterative but would not improve the asymptotic complexity — concatenation inherently requires copying the first list. At best, an accumulator decreases the constant factor, but complicating the code is likely to increase it. Never add an accumulator merely out of habit.

Why the first list must be copied

Because OCaml lists are immutable, append cannot modify the last cons cell of the first list to point to the second list. Instead, it must copy every cons cell of the first list, with the final copy pointing to the second list. The second list is shared, not copied:

Original:  [1] --> [2] --> [3] --> []

Copy:      [1] --> [2] --> [3] --> [4] --> []
                                  ^
                                  | (shared)
Original:                  [4] --> []

Polymorphic type

Append’s type 'a list -> 'a list -> 'a list tells us two lists can be joined only if their element types agree. The result has the same element type.