925 Intermediate

925-list-operations — List Operations

Functional Programming

Tutorial

The Problem

Lists are the fundamental data structure of functional programming. OCaml's standard library is built around singly-linked list: head::tail destructuring, recursive definitions, and higher-order functions like map, filter, and fold. Rust uses Vec<T> as the workhorse — heap-allocated, contiguous, with O(1) indexed access — but supports functional-style operations through the Iterator trait. Learning to express classical list algorithms in Rust illuminates both the idioms of functional programming and the differences between Rust's ownership-based and OCaml's GC-based memory models.

🎯 Learning Outcomes

• Implement length, sum, append, reverse, map, and filter using Rust iterators

• Understand the recursive equivalent of each operation using slice pattern matching

• Recognize the difference between recursive list patterns in OCaml and slice patterns in Rust

• Use split_first() as the Rust equivalent of OCaml's head :: tail destructuring

• Compare iterator-based and recursive implementations of the same operations

Code Example

pub fn sum(list: &[i64]) -> i64 {
    list.iter().sum()
}

let rec sum = function
  | [] -> 0
  | head :: tail -> head + sum tail

Key Differences

Data structure: OCaml uses singly-linked immutable lists (prepend O(1), indexed access O(n)); Rust uses Vec<T> (append O(1) amortized, indexed access O(1)).

Pattern matching: OCaml's x :: xs destructures a list; Rust uses split_first() or [head, rest @ ..] slice patterns on &[T].

Sharing: OCaml lists share tails via GC (prepend creates shared structure); Rust Vec clones or moves data.

Tail recursion: OCaml relies on TCO for stack-safe recursion; Rust iterators eliminate the stack depth concern for production use.

OCaml Approach

OCaml's List module provides all these as library functions, each implemented recursively on the singly-linked list structure. let rec length = function | [] -> 0 | _ :: t -> 1 + length t. List.rev_append is the tail-recursive reverse. OCaml's pattern matching on x :: xs is syntactically integrated; Rust's split_first() and [head, rest @ ..] patterns serve the same purpose but with ownership/borrowing constraints. OCaml lists are persistent and shared via GC; Rust Vec is owned and mutable.

Full Source

#![allow(clippy::all)]
/// List Operations: fundamental building blocks in functional programming.
///
/// In OCaml, lists are the bread and butter — singly-linked, immutable, with
/// pattern matching driving recursion. In Rust, Vec is the workhorse, but we
/// can still express recursive/functional patterns using slices and iterators.

// ── Idiomatic Rust: Iterator-based ──────────────────────────────────────────

/// Length using iterator (idiomatic Rust just uses `.len()`, but here we show fold)
pub fn length<T>(list: &[T]) -> usize {
    list.iter().fold(0, |acc, _| acc + 1)
}

/// Sum using iterators
pub fn sum(list: &[i64]) -> i64 {
    list.iter().sum()
}

/// Append two slices into a new Vec
pub fn append<T: Clone>(a: &[T], b: &[T]) -> Vec<T> {
    a.iter().chain(b.iter()).cloned().collect()
}

/// Reverse using iterators
pub fn reverse<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter().rev().cloned().collect()
}

/// Map: apply a function to each element
pub fn map<T, U>(list: &[T], f: impl Fn(&T) -> U) -> Vec<U> {
    list.iter().map(f).collect()
}

/// Filter: keep elements satisfying a predicate
pub fn filter<T: Clone>(list: &[T], pred: impl Fn(&T) -> bool) -> Vec<T> {
    list.iter().filter(|x| pred(x)).cloned().collect()
}

// ── Functional/Recursive style (closer to OCaml) ───────────────────────────

/// Recursive length using slice pattern matching.
/// Note: Rust slices don't have head::tail destructuring like OCaml,
/// so we use `split_first()` or index-based patterns.
pub fn length_recursive<T>(list: &[T]) -> usize {
    match list.split_first() {
        None => 0,
        Some((_, tail)) => 1 + length_recursive(tail),
    }
}

/// Recursive sum
pub fn sum_recursive(list: &[i64]) -> i64 {
    match list.split_first() {
        None => 0,
        Some((&head, tail)) => head + sum_recursive(tail),
    }
}

/// Recursive append — builds result by consing head onto recursive call.
/// In Rust, we must allocate a new Vec each time (no persistent list sharing).
pub fn append_recursive<T: Clone>(a: &[T], b: &[T]) -> Vec<T> {
    match a.split_first() {
        None => b.to_vec(),
        Some((head, tail)) => {
            let mut result = vec![head.clone()];
            result.extend(append_recursive(tail, b));
            result
        }
    }
}

// ── Tail-recursive style ───────────────────────────────────────────────────

/// Tail-recursive length with accumulator (mirrors OCaml's aux pattern)
pub fn length_tail_recursive<T>(list: &[T]) -> usize {
    fn aux<T>(acc: usize, list: &[T]) -> usize {
        match list.split_first() {
            None => acc,
            Some((_, tail)) => aux(acc + 1, tail),
        }
    }
    aux(0, list)
}

/// Tail-recursive sum
pub fn sum_tail_recursive(list: &[i64]) -> i64 {
    fn aux(acc: i64, list: &[i64]) -> i64 {
        match list.split_first() {
            None => acc,
            Some((&head, tail)) => aux(acc + head, tail),
        }
    }
    aux(0, list)
}

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

    #[test]
    fn test_length_empty() {
        assert_eq!(length::<i32>(&[]), 0);
        assert_eq!(length_recursive::<i32>(&[]), 0);
        assert_eq!(length_tail_recursive::<i32>(&[]), 0);
    }

    #[test]
    fn test_length_nonempty() {
        assert_eq!(length(&[1, 2, 3]), 3);
        assert_eq!(length_recursive(&[1, 2, 3]), 3);
        assert_eq!(length_tail_recursive(&[1, 2, 3]), 3);
    }

    #[test]
    fn test_sum_variants() {
        assert_eq!(sum(&[]), 0);
        assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_recursive(&[10, -5, 3]), 8);
        assert_eq!(sum_tail_recursive(&[100]), 100);
    }

    #[test]
    fn test_append() {
        assert_eq!(append(&[1, 2], &[3, 4]), vec![1, 2, 3, 4]);
        assert_eq!(append::<i32>(&[], &[1]), vec![1]);
        assert_eq!(append_recursive(&[1], &[2, 3]), vec![1, 2, 3]);
    }

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

    #[test]
    fn test_map_and_filter() {
        assert_eq!(map(&[1, 2, 3], |x| x * 2), vec![2, 4, 6]);
        assert_eq!(filter(&[1, 2, 3, 4, 5], |x| x % 2 == 0), vec![2, 4]);
        assert_eq!(map::<i32, i32>(&[], |x| x + 1), Vec::<i32>::new());
    }

    #[test]
    fn test_large_list() {
        let big: Vec<i64> = (1..=1000).collect();
        assert_eq!(sum(&big), 500500);
        assert_eq!(length(&big), 1000);
    }
}

(* List Operations: fundamental recursive patterns in OCaml *)

(* ── Basic recursive versions ─────────────────────────────────── *)

let rec length = function
  | [] -> 0
  | _ :: tail -> 1 + length tail

let rec sum = function
  | [] -> 0
  | head :: tail -> head + sum tail

let rec append l1 l2 =
  match l1 with
  | [] -> l2
  | head :: tail -> head :: append tail l2

let rec reverse = function
  | [] -> []
  | head :: tail -> reverse tail @ [head]

(* ── Tail-recursive versions (efficient, no stack overflow) ──── *)

let length_tr lst =
  let rec aux acc = function
    | [] -> acc
    | _ :: tail -> aux (acc + 1) tail
  in aux 0 lst

let sum_tr lst =
  let rec aux acc = function
    | [] -> acc
    | h :: t -> aux (acc + h) t
  in aux 0 lst

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

(* ── Higher-order: map, filter ───────────────────────────────── *)

let rec map f = function
  | [] -> []
  | h :: t -> f h :: map f t

let rec filter pred = function
  | [] -> []
  | h :: t -> if pred h then h :: filter pred t else filter pred t

(* ── Tests ────────────────────────────────────────────────────── *)
let () =
  assert (length [] = 0);
  assert (length [1;2;3] = 3);
  assert (sum [1;2;3;4;5] = 15);
  assert (append [1;2] [3;4] = [1;2;3;4]);
  assert (reverse [1;2;3] = [3;2;1]);
  assert (length_tr [1;2;3] = 3);
  assert (sum_tr [1;2;3;4;5] = 15);
  assert (reverse_tr [1;2;3] = [3;2;1]);
  assert (map (fun x -> x * 2) [1;2;3] = [2;4;6]);
  assert (filter (fun x -> x mod 2 = 0) [1;2;3;4;5] = [2;4]);
  print_endline "✓ All list operations tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_length_empty() {
        assert_eq!(length::<i32>(&[]), 0);
        assert_eq!(length_recursive::<i32>(&[]), 0);
        assert_eq!(length_tail_recursive::<i32>(&[]), 0);
    }

    #[test]
    fn test_length_nonempty() {
        assert_eq!(length(&[1, 2, 3]), 3);
        assert_eq!(length_recursive(&[1, 2, 3]), 3);
        assert_eq!(length_tail_recursive(&[1, 2, 3]), 3);
    }

    #[test]
    fn test_sum_variants() {
        assert_eq!(sum(&[]), 0);
        assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum_recursive(&[10, -5, 3]), 8);
        assert_eq!(sum_tail_recursive(&[100]), 100);
    }

    #[test]
    fn test_append() {
        assert_eq!(append(&[1, 2], &[3, 4]), vec![1, 2, 3, 4]);
        assert_eq!(append::<i32>(&[], &[1]), vec![1]);
        assert_eq!(append_recursive(&[1], &[2, 3]), vec![1, 2, 3]);
    }

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

    #[test]
    fn test_map_and_filter() {
        assert_eq!(map(&[1, 2, 3], |x| x * 2), vec![2, 4, 6]);
        assert_eq!(filter(&[1, 2, 3, 4, 5], |x| x % 2 == 0), vec![2, 4]);
        assert_eq!(map::<i32, i32>(&[], |x| x + 1), Vec::<i32>::new());
    }

    #[test]
    fn test_large_list() {
        let big: Vec<i64> = (1..=1000).collect();
        assert_eq!(sum(&big), 500500);
        assert_eq!(length(&big), 1000);
    }
}

Deep Comparison

List Operations: OCaml vs Rust

The Core Insight

List operations are where functional programming shines — expressing computation as recursive transformations rather than indexed loops. OCaml's singly-linked lists with pattern matching feel natural; Rust's Vec and iterators offer a different but equally expressive approach, with ownership making aliasing explicit.

OCaml Approach

OCaml lists are singly-linked and immutable. Pattern matching with head :: tail destructures the list naturally:

let rec sum = function
  | [] -> 0
  | head :: tail -> head + sum tail

The :: constructor is O(1) prepend, and tail-recursive versions use an accumulator to avoid stack overflow. Higher-order functions like map and filter are built the same way — recursive descent with pattern matching.

Rust Approach

Rust uses Vec<T> (contiguous, growable array) rather than linked lists. Iterator chains provide the functional style:

pub fn sum(list: &[i64]) -> i64 {
    list.iter().sum()
}

For recursive patterns, split_first() gives Option<(&T, &[T])>, mimicking OCaml's head/tail destructuring. Ownership means we must decide: borrow with &[T] or consume with Vec<T>.

Key Differences

Aspect	OCaml	Rust
List type	Singly-linked (immutable)	Vec (contiguous array)
Destructuring	`h :: t` pattern	`split_first()` method
Memory	GC handles everything	Ownership: borrow or clone
Prepend	O(1) with `::`	O(n) with `insert(0, x)`
Append	O(n) with `@`	O(1) amortized with `push`
Tail recursion	Compiler optimizes TCO	Not guaranteed — prefer iterators
Idiomatic style	Recursion + pattern matching	Iterator chains

What Rust Learners Should Notice

• Iterators replace recursion: Rust's iterator combinators (map, filter, fold, sum) are zero-cost abstractions — they compile to the same code as hand-written loops.

• **No free head :: tail**: Rust slices don't destructure like OCaml lists. split_first() is the closest equivalent, returning Option<(&T, &[T])>.

• Ownership matters for append: In OCaml, append [1;2] [3;4] shares the tail. In Rust, you must clone or move elements.

• Tail recursion isn't guaranteed: Unlike OCaml, Rust doesn't guarantee TCO. For large lists, prefer iterators or explicit loops.

Exercises

Implement zip_lists<A, B>(a: &[A], b: &[B]) -> Vec<(A, B)> both iteratively and recursively.

Write flatten<T: Clone>(nested: &[Vec<T>]) -> Vec<T> using both .iter().flatten() and a manual recursive approach.

Implement group_consecutive<T: Eq + Clone>(data: &[T]) -> Vec<Vec<T>> recursively using slice patterns.

Open Source Repos

functional-rust

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

Rust

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

List Operations: OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Key Differences

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos