005: Reverse a List

Difficulty: ⭐ Level: Beginner Flip the order of elements in a list — and choose whether to create a copy or reverse in place.

The Problem This Solves

Reversing a list comes up constantly: displaying history newest-first, reversing a traversal order, building a result by prepending items then flipping at the end. Every language handles it a bit differently. Python's `lst[::-1]` creates a copy. JavaScript's `arr.reverse()` mutates in place (and many JS programmers have been surprised to learn this). Java's `Collections.reverse()` also mutates. In functional languages like OCaml, everything creates a new list — there's no mutation. Rust is explicit about the choice. Want a new reversed copy? `iter().rev().collect()`. Want to reverse the existing data in place (faster, no allocation)? `slice.reverse()`. The type system makes the difference obvious: in-place requires `&mut`, creating a copy requires `T: Clone`.

The Intuition

# Python
original = [1, 2, 3, 4]
reversed_copy = original[::-1]   # new list, original unchanged
original.reverse()                # in-place, original is now [4, 3, 2, 1]

// JavaScript — careful! this mutates!
arr.reverse()  // [4, 3, 2, 1] — arr is changed
// To get a copy: [...arr].reverse()

// Rust — the choice is explicit in the function signature

// Creates a new Vec (original unchanged)
let reversed: Vec<_> = list.iter().rev().cloned().collect();

// Reverses in place (no allocation)
list.reverse();  // requires `mut` — you can't do this by accident

The `iter().rev()` trick is elegant: `.rev()` doesn't actually move any data — it just reverses the direction the iterator walks. Only `.collect()` materializes the result into a new `Vec`.

How It Works in Rust

// Option 1: Create a reversed copy (immutable input)
fn rev<T: Clone>(list: &[T]) -> Vec<T> {
 list.iter().rev().cloned().collect()
 //          ^^^^              ^^^^^^
 //          lazy reverse      now allocate
}

// Option 2: Reverse in place (zero allocation)
fn rev_mut<T>(list: &mut [T]) {
 list.reverse();  // swaps elements: O(n) time, O(1) extra space
}

Why `clone()`? The input is a borrowed slice `&[T]` — we don't own those values. To put them into a new `Vec`, we need to copy them. The `T: Clone` bound says "this only works for types that support copying." The functional fold version (mirrors OCaml's accumulator pattern):

// Mirrors: let rec aux acc = function h :: t -> aux (h :: acc) t
// Note: insert(0, ...) is O(n²) — use iter().rev() instead
fn rev_fold<T: Clone>(list: &[T]) -> Vec<T> {
 list.iter().fold(Vec::new(), |mut acc, x| {
     acc.insert(0, x.clone());  // prepend — educational, not optimal
     acc
 })
}

What This Unlocks

Processing history or logs in reverse chronological order without disturbing the original
Building lists by appending then reversing — the classic functional pattern for O(n) list construction
Bidirectional iteration — `iter().rev()` works on any slice without creating a copy

Key Differences

Concept	OCaml	Rust
Always creates new list	Yes (GC manages memory)	Optional — in-place possible
In-place reversal	Not available	`slice.reverse()` with `&mut`
Functional accumulator	`h :: acc` (O(1) prepend)	`iter().rev().collect()`
Lazy reversal	Not applicable	`iter().rev()` — no data moved
Requires `Clone`	Implicit copy on GC heap	Explicit `T: Clone` bound
Stack safety	TCO via accumulator	Iterators — no stack concern

// Reverse a list

// Idiomatic Rust: iterator reversal (lazy)
fn rev<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter().rev().cloned().collect()
}

// In-place mutation (imperative style)
fn rev_mut<T>(list: &mut [T]) {
    list.reverse();
}

// Functional with fold (like OCaml accumulator)
fn rev_fold<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter().fold(Vec::new(), |mut acc, x| {
        acc.insert(0, x.clone());
        acc
    })
}

// Tail-recursive (educational)
fn rev_recursive<T: Clone>(list: &[T]) -> Vec<T> {
    fn aux<T: Clone>(mut acc: Vec<T>, list: &[T]) -> Vec<T> {
        match list {
            [] => acc,
            [h, rest @ ..] => {
                acc.insert(0, h.clone());
                aux(acc, rest)
            }
        }
    }
    aux(Vec::new(), list)
}

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

    #[test]
    fn test_rev() {
        let empty: Vec<i32> = vec![];
        assert_eq!(rev(&empty), empty);
        assert_eq!(rev(&[1]), vec![1]);
        assert_eq!(rev(&[1, 2, 3, 4]), vec![4, 3, 2, 1]);
        assert_eq!(rev(&["a", "b", "c"]), vec!["c", "b", "a"]);
    }

    #[test]
    fn test_rev_mut() {
        let mut list = vec![1, 2, 3, 4];
        rev_mut(&mut list);
        assert_eq!(list, vec![4, 3, 2, 1]);
    }
}

fn main() {
    println!("rev([1,2,3,4]) = {:?}", rev(&[1, 2, 3, 4]));
    println!("✓ Rust tests passed");
}

(* Reverse a list *)

(* Tail-recursive with accumulator *)
let rev list =
  let rec aux acc = function
    | [] -> acc
    | h :: t -> aux (h :: acc) t
  in
  aux [] list

(* Tests *)
let () =
  assert (rev [] = []);
  assert (rev [1] = [1]);
  assert (rev [1; 2; 3; 4] = [4; 3; 2; 1]);
  assert (rev ["a"; "b"; "c"] = ["c"; "b"; "a"]);
  print_endline "✓ OCaml tests passed"

📊 Detailed Comparison

Comparison: Reverse a List

OCaml

🐪 Show OCaml equivalent

let rev list =
let rec aux acc = function
 | [] -> acc
 | h :: t -> aux (h :: acc) t
in aux [] list

Rust — Idiomatic (iterator)

pub fn reverse<T: Clone>(slice: &[T]) -> Vec<T> {
 slice.iter().rev().cloned().collect()
}

Rust — Fold (mirrors OCaml accumulator)

pub fn reverse_fold<T: Clone>(slice: &[T]) -> Vec<T> {
 slice.iter().fold(Vec::new(), |mut acc, item| {
     acc.insert(0, item.clone());
     acc
 })
}

Rust — Recursive

pub fn reverse_recursive<T: Clone>(slice: &[T]) -> Vec<T> {
 fn aux<T: Clone>(acc: Vec<T>, slice: &[T]) -> Vec<T> {
     match slice {
         [] => acc,
         [head, rest @ ..] => {
             let mut new_acc = vec![head.clone()];
             new_acc.extend(acc);
             aux(new_acc, rest)
         }
     }
 }
 aux(Vec::new(), slice)
}

Rust — In-place (owned data)

pub fn reverse_in_place<T>(slice: &mut [T]) {
 slice.reverse();
}

Comparison Table

Aspect	OCaml	Rust (idiomatic)	Rust (in-place)
Allocation	New list	New Vec	None
Complexity	O(n)	O(n)	O(n)
Ownership	Immutable	Borrows input	Mutates input
Trait needed	None	`Clone`	None
Prepend cost	O(1) cons	O(n) insert(0)	N/A

Type Signatures

OCaml: `val rev : 'a list -> 'a list`
Rust: `fn reverse<T: Clone>(slice: &[T]) -> Vec<T>`
Rust (in-place): `fn reverse_in_place<T>(slice: &mut [T])`

Takeaways

1. OCaml's cons (`::`) is O(1) prepend — perfect for accumulator-based reversal; Rust's Vec prepend is O(n) — use `rev()` iterator instead 2. Rust's `iter().rev()` is lazy — it changes direction without traversing, then `collect()` builds the result in one pass 3. In-place reversal (`slice.reverse()`) is uniquely Rust — OCaml's immutable lists can't be mutated 4. The `Clone` trait bound makes copying explicit — OCaml copies values implicitly during pattern matching 5. The accumulator pattern translates directly but isn't idiomatic Rust — iterators express the same intent more clearly