Reversing Lists

Naive reverse: nrev — O(n²)

let rec nrev = function
  | [] -> []
  | x :: xs -> (nrev xs) @ [x]
(* val nrev : 'a list -> 'a list = <fun> *)

This reverses by recursively reversing the tail and appending the head as a singleton list at the end. A trace:

nrev [a; b; c] => (nrev [b; c]) @ [a]
               => ((nrev [c]) @ [b]) @ [a]
               => (((nrev []) @ [c]) @ [b]) @ [a]
               => (([] @ [c]) @ [b]) @ [a]
               => [c; b; a]

Why it is inefficient: each call to @ copies its first argument. For a list of length n:

• Reverse the tail (n-1 elements): n-1 conses in append
• Then cons x onto []: 1 cons
• Total for this step: n conses
• Reversing the tail requires n-1 more conses, and so forth

Total conses: $0 + 1 + 2 + \dots + n = \frac{n(n+1)}{2} = O(n^2)$

Space complexity is O(n) because the copies do not all exist at the same time.

Efficient reverse: rev_app — O(n)

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

rev_app xs ys reverses the elements of xs and prepends them to ys. Trace:

rev_app [a; b; c] [] => rev_app [b; c] [a]
                      => rev_app [c] [b; a]
                      => rev_app [] [c; b; a]
                      => [c; b; a]

This performs exactly n conses for an n-element list — one per element as it moves from the input to the accumulator. Time is O(n), space is O(1) (tail-recursive).

The wrapper hides the accumulator:

let rev xs = rev_app xs []
(* val rev : 'a list -> 'a list = <fun> *)

Reduction in strength

The key improvement comes from replacing an expensive operation (@, which is O(n)) with a series of cheap operations (::, which is O(1)). This technique is called reduction in strength and is a common pattern in algorithm design. It originated when hardware lacked multiply instructions — repeated addition was cheaper than multiplication.

Why consing to an accumulator reverses

Cons adds to the front of a list, so as elements are consed to the accumulator in order, the accumulator builds up in reverse:

Step	Input remaining	Accumulator
Start	[a; b; c]	[]
After a	[b; c]	[a]
After b	[c]	[b; a]
After c	[]	[c; b; a]

If the reverse order in the accumulator is undesirable, an extra call to rev at the end fixes it — but that doubles the cost. Sometimes the iterative function can be slower than the recursive one if an extra reversal is needed.