928 Fundamental

928-reverse-list — Reverse List

Functional Programming

Tutorial

The Problem

Reversing a list is the "hello world" of functional data structure algorithms. It exercises the core skill of list recursion and accumulator-based tail recursion. The naive recursive version (rev(t) ++ [h]) is O(n²) due to append at each step. The accumulator version (rev_acc(t, h::acc)) is O(n) and tail-recursive — the standard functional programming solution. OCaml's List.rev uses this pattern. Rust's .rev() iterator adapter is O(1) (lazy reversal); .iter().rev().collect() is O(n). This example shows all three approaches.

🎯 Learning Outcomes

• Implement list reversal using Rust's iterator .rev() adapter

• Implement tail-recursive reversal with an accumulator using slice patterns

• Understand why the naive recursive reversal is O(n²) while the accumulator version is O(n)

• Use list.reverse() for in-place mutation as the imperative style

• Compare with OCaml's List.rev and the functional accumulator pattern

Code Example

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

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

Key Differences

In-place vs functional: Rust has reverse() for in-place mutation (not available for OCaml's immutable lists); OCaml always creates a new list.

Iterator laziness: Rust .rev() is lazy — it reverses the traversal direction without allocation until .collect() is called; OCaml's List.rev is always eager.

Accumulator style: Both languages use the accumulator pattern for O(n) functional reversal; Rust uses an explicit Vec as the accumulator.

Stack safety: OCaml relies on TCO for the accumulator version; Rust's iterator approach avoids deep recursion entirely.

OCaml Approach

List.rev: 'a list -> 'a list is the standard library function, implemented as: let rev xs = let rec aux acc = function | [] -> acc | x :: rest -> aux (x :: acc) rest in aux [] xs. The accumulator builds the reversed list by prepending, which is O(1) per element. List.rev_append xs acc reverses xs onto acc in one pass. OCaml's tail-call optimization makes the accumulator version stack-safe for any length.

Full Source

#![allow(clippy::all)]
// 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]);
    }
}

(* 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"

✓ Tests Rust test suite

#[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]);
    }
}

Deep Comparison

Comparison: Reverse a List

OCaml

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

OCaml's cons (::) is O(1) prepend — perfect for accumulator-based reversal; Rust's Vec prepend is O(n) — use rev() iterator instead

Rust's iter().rev() is lazy — it changes direction without traversing, then collect() builds the result in one pass

In-place reversal (slice.reverse()) is uniquely Rust — OCaml's immutable lists can't be mutated

The Clone trait bound makes copying explicit — OCaml copies values implicitly during pattern matching

The accumulator pattern translates directly but isn't idiomatic Rust — iterators express the same intent more clearly

Exercises

Implement rev_words(sentence: &str) -> String that reverses the word order but not individual characters.

Write rotate_left<T: Clone>(data: &[T], n: usize) -> Vec<T> using rev operations on two sub-slices.

Implement palindrome_indices(data: &[i32]) -> Vec<usize> using a reverse to find all elements that appear at the same position in the reversed array.

Open Source Repos

functional-rust

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

Rust