005 Fundamental

005 — Reverse a List

Functional Programming

Tutorial

The Problem

Reversing a list is a deceptively simple problem that illuminates a critical performance trap in functional programming: naive recursive reverse is O(n²) because each recursive call appends to the end. The solution — the accumulator pattern — is O(n) and is the prototype for tail-recursive programming. Understanding this transformation is essential before working with any recursive data structure.

The accumulator pattern generalizes: it replaces "build result on the way back up the stack" with "carry the result forward as a parameter". This is exactly what makes a function tail-recursive, allowing the compiler to optimize it into a loop. This pattern appears in reverse, flatten, map, filter, and virtually every recursive list operation.

🎯 Learning Outcomes

• Implement list reversal in four ways: built-in, iterator, fold, and recursive

• Understand why naive recursive reverse is O(n²) and how the accumulator fixes it

• Use the fold pattern to carry state forward through a list

• Recognize when recursion can be replaced with an accumulator for stack safety

• Understand Rust's in-place reverse() vs immutable iterator-based reversal

• Use Rust's built-in v.reverse() for in-place O(n) mutation and .iter().rev().collect() for an immutable O(n) functional reverse

Code Example

#![allow(clippy::all)]
// 005: Reverse a List

// Approach 1: Built-in (in-place)
fn reverse_inplace(v: &mut Vec<i32>) {
    v.reverse();
}

// Approach 2: Iterator-based (new Vec)
fn reverse_iter(v: &[i32]) -> Vec<i32> {
    v.iter().rev().copied().collect()
}

// Approach 3: Fold-based (accumulator pattern)
fn reverse_fold(v: &[i32]) -> Vec<i32> {
    v.iter().fold(vec![], |mut acc, &x| {
        acc.insert(0, x);
        acc
    })
}

// Approach 3b: Recursive
fn reverse_recursive(v: &[i32]) -> Vec<i32> {
    if v.is_empty() {
        vec![]
    } else {
        let mut rest = reverse_recursive(&v[1..]);
        rest.push(v[0]);
        rest
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_reverse_inplace() {
        let mut v = vec![1, 2, 3, 4, 5];
        reverse_inplace(&mut v);
        assert_eq!(v, vec![5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_reverse_iter() {
        assert_eq!(reverse_iter(&[1, 2, 3, 4, 5]), vec![5, 4, 3, 2, 1]);
        assert_eq!(reverse_iter(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_reverse_fold() {
        assert_eq!(reverse_fold(&[1, 2, 3]), vec![3, 2, 1]);
    }

    #[test]
    fn test_reverse_recursive() {
        assert_eq!(reverse_recursive(&[1, 2, 3, 4, 5]), vec![5, 4, 3, 2, 1]);
        assert_eq!(reverse_recursive(&[42]), vec![42]);
        assert_eq!(reverse_recursive(&[]), Vec::<i32>::new());
    }
}

(* 005: Reverse a List *)

(* Approach 1: Built-in *)
let reverse_builtin lst = List.rev lst

(* Approach 2: Naive recursive — O(n^2) *)
let rec reverse_naive = function
  | [] -> []
  | x :: xs -> reverse_naive xs @ [x]

(* Approach 3: Tail-recursive with accumulator — O(n) *)
let reverse_acc lst =
  let rec aux acc = function
    | [] -> acc
    | x :: xs -> aux (x :: acc) xs
  in
  aux [] lst

(* Tests *)
let () =
  assert (reverse_builtin [1; 2; 3; 4; 5] = [5; 4; 3; 2; 1]);
  assert (reverse_builtin [] = []);
  assert (reverse_naive [1; 2; 3] = [3; 2; 1]);
  assert (reverse_acc [1; 2; 3; 4; 5] = [5; 4; 3; 2; 1]);
  assert (reverse_acc [] = []);
  assert (reverse_acc [42] = [42]);
  Printf.printf "✓ All tests passed\n"

Key Differences

In-place vs functional: Rust's Vec::reverse() mutates in place — O(n), zero allocation. OCaml's List.rev always allocates a new list (immutable data structure constraint).

Tail-call optimization: OCaml guarantees TCO for tail-recursive functions. Rust does not — the accumulator-based version should be implemented as a loop, not as recursion, for large inputs.

Stack risk: A naive recursive reverse on a list of 100,000 elements will stack overflow in Rust but not in OCaml (after TCO).

**fold_left direction**: Both languages have left-fold and right-fold. Using fold_left with cons (x :: acc) naturally builds a reversed list — this is a fundamental pattern.

In-place vs immutable: Rust's v.reverse() mutates in place — no allocation. OCaml lists are immutable; "reversing" always creates a new list.

O(n) accumulator: Both languages use the accumulator pattern for O(n) reverse. Rust's fold achieves this without recursion; OCaml uses rev_append l [].

TCO: The tail-recursive OCaml version is safe for any length. The recursive Rust version will stack-overflow for large inputs — use fold or .rev() in production code.

**insert(0, _) is O(n):** Rust's Vec::insert(0, x) shifts all elements right — making the fold-based reverse O(n²). OCaml's list prepend x :: acc is O(1).

**.rev() is lazy:** Rust's .iter().rev() returns a Rev<Iter> — a zero-cost adapter that reads backwards. No allocation occurs until .collect().

OCaml Approach

OCaml's standard library provides List.rev and List.rev_append. The classic teaching version is let rec rev_acc acc = function [] -> acc | x :: t -> rev_acc (x :: acc) t. Because OCaml guarantees tail-call optimization, rev_acc [] lst is compiled into a loop. The List.fold_left version List.fold_left (fun acc x -> x :: acc) [] lst is equivalent and idiomatic.

Full Source

#![allow(clippy::all)]
// 005: Reverse a List

// Approach 1: Built-in (in-place)
fn reverse_inplace(v: &mut Vec<i32>) {
    v.reverse();
}

// Approach 2: Iterator-based (new Vec)
fn reverse_iter(v: &[i32]) -> Vec<i32> {
    v.iter().rev().copied().collect()
}

// Approach 3: Fold-based (accumulator pattern)
fn reverse_fold(v: &[i32]) -> Vec<i32> {
    v.iter().fold(vec![], |mut acc, &x| {
        acc.insert(0, x);
        acc
    })
}

// Approach 3b: Recursive
fn reverse_recursive(v: &[i32]) -> Vec<i32> {
    if v.is_empty() {
        vec![]
    } else {
        let mut rest = reverse_recursive(&v[1..]);
        rest.push(v[0]);
        rest
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_reverse_inplace() {
        let mut v = vec![1, 2, 3, 4, 5];
        reverse_inplace(&mut v);
        assert_eq!(v, vec![5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_reverse_iter() {
        assert_eq!(reverse_iter(&[1, 2, 3, 4, 5]), vec![5, 4, 3, 2, 1]);
        assert_eq!(reverse_iter(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_reverse_fold() {
        assert_eq!(reverse_fold(&[1, 2, 3]), vec![3, 2, 1]);
    }

    #[test]
    fn test_reverse_recursive() {
        assert_eq!(reverse_recursive(&[1, 2, 3, 4, 5]), vec![5, 4, 3, 2, 1]);
        assert_eq!(reverse_recursive(&[42]), vec![42]);
        assert_eq!(reverse_recursive(&[]), Vec::<i32>::new());
    }
}

(* 005: Reverse a List *)

(* Approach 1: Built-in *)
let reverse_builtin lst = List.rev lst

(* Approach 2: Naive recursive — O(n^2) *)
let rec reverse_naive = function
  | [] -> []
  | x :: xs -> reverse_naive xs @ [x]

(* Approach 3: Tail-recursive with accumulator — O(n) *)
let reverse_acc lst =
  let rec aux acc = function
    | [] -> acc
    | x :: xs -> aux (x :: acc) xs
  in
  aux [] lst

(* Tests *)
let () =
  assert (reverse_builtin [1; 2; 3; 4; 5] = [5; 4; 3; 2; 1]);
  assert (reverse_builtin [] = []);
  assert (reverse_naive [1; 2; 3] = [3; 2; 1]);
  assert (reverse_acc [1; 2; 3; 4; 5] = [5; 4; 3; 2; 1]);
  assert (reverse_acc [] = []);
  assert (reverse_acc [42] = [42]);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_reverse_inplace() {
        let mut v = vec![1, 2, 3, 4, 5];
        reverse_inplace(&mut v);
        assert_eq!(v, vec![5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_reverse_iter() {
        assert_eq!(reverse_iter(&[1, 2, 3, 4, 5]), vec![5, 4, 3, 2, 1]);
        assert_eq!(reverse_iter(&[]), Vec::<i32>::new());
    }

    #[test]
    fn test_reverse_fold() {
        assert_eq!(reverse_fold(&[1, 2, 3]), vec![3, 2, 1]);
    }

    #[test]
    fn test_reverse_recursive() {
        assert_eq!(reverse_recursive(&[1, 2, 3, 4, 5]), vec![5, 4, 3, 2, 1]);
        assert_eq!(reverse_recursive(&[42]), vec![42]);
        assert_eq!(reverse_recursive(&[]), Vec::<i32>::new());
    }
}

Deep Comparison

Core Insight

Reversing a list reveals the importance of accumulator patterns. The naive approach (reverse tail, append head) creates O(n²) work. The tail-recursive approach (prepend to accumulator) achieves O(n).

OCaml Approach

• List.rev — standard library, O(n)

• Naive: rev xs @ [x] — O(n²)

• Tail-recursive: accumulator pattern with x :: acc

Rust Approach

• .reverse() — in-place mutation, O(n)

• .iter().rev().collect() — creates new reversed Vec

• Manual fold: .fold(vec![], |acc, x| ...)

Comparison Table

Approach	OCaml	Rust
Built-in	`List.rev`	`.reverse()` / `.rev()`
Naive recursive	`rev tail @ [head]`	`rec_reverse(&v[1..]).push(v[0])`
Tail-recursive	`aux (x::acc) xs`	loop with accumulator
Complexity (good)	O(n)	O(n)

Exercises

Tail-safe recursive reverse: Rewrite reverse_recursive using an explicit accumulator argument so it is tail-recursive in structure (even though Rust won't TCO it, understand the pattern).

Palindrome check: Use reverse_iter to implement is_palindrome(v: &[i32]) -> bool in one line. Then implement a zero-copy version using v.iter().eq(v.iter().rev()).

Rotate: Write rotate_left(v: &[i32], n: usize) -> Vec<i32> that moves the first n elements to the end, using slices and extend rather than repeated reversal.

In-place partial reverse: Write reverse_segment(v: &mut Vec<i32>, start: usize, end: usize) that reverses elements in the range start..end in place — building block for the rotational algorithm.

Palindrome check via reverse: Use reverse_iter to implement is_palindrome(v: &[i32]) -> bool that checks whether a slice equals its own reverse, without allocating twice.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust