002 Intermediate

002 — List Operations

Functional Programming

Tutorial

The Problem

Linked lists are the canonical data structure of functional programming. In Haskell, OCaml, and Lisp, the list is the primary collection type and virtually all standard library functions operate on it. Even in languages where arrays are preferred at runtime, understanding the core list operations — head, tail, length, append, reverse — gives insight into structural recursion and the accumulator pattern.

The recursive structure of lists (an element prepended to another list) maps directly to recursive function definitions. This correspondence between data shape and function shape is the essence of pattern matching on algebraic data types, used extensively in compilers, interpreters, and proof assistants.

🎯 Learning Outcomes

• Understand head/tail decomposition as the basis for structural recursion

• Implement list operations iteratively, recursively, and with tail-recursive accumulators

• Recognize the performance implications of naive recursion vs accumulator style

• Use Vec methods that correspond to functional list operations

• Understand why rev_acc (reverse with accumulator) is O(n) while naive reverse is O(n²)

• Understand why Vec::append is O(|a|) while OCaml's @ copies only the left list (structural sharing of the right)

• Apply tail-recursive accumulator as the template for stack-safe recursion on large inputs

Code Example

#![allow(clippy::all)]
// 002: List Operations
// Core list operations: head, tail, length, append, reverse

// Approach 1: Vec methods
fn head(v: &[i32]) -> Option<&i32> {
    v.first()
}

fn tail(v: &[i32]) -> Option<&[i32]> {
    if v.is_empty() {
        None
    } else {
        Some(&v[1..])
    }
}

fn length(v: &[i32]) -> usize {
    v.len()
}

fn append(a: &[i32], b: &[i32]) -> Vec<i32> {
    let mut result = a.to_vec();
    result.extend_from_slice(b);
    result
}

fn reverse(v: &[i32]) -> Vec<i32> {
    v.iter().rev().copied().collect()
}

// Approach 2: Recursive (functional style)
fn rec_length(v: &[i32]) -> usize {
    if v.is_empty() {
        0
    } else {
        1 + rec_length(&v[1..])
    }
}

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

// Approach 3: Tail-recursive with accumulator
fn rev_acc(v: &[i32]) -> Vec<i32> {
    fn aux(slice: &[i32], acc: Vec<i32>) -> Vec<i32> {
        if slice.is_empty() {
            acc
        } else {
            let mut new_acc = vec![slice[0]];
            new_acc.extend(acc);
            aux(&slice[1..], new_acc)
        }
    }
    aux(v, vec![])
}

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

    #[test]
    fn test_head() {
        assert_eq!(head(&[1, 2, 3]), Some(&1));
        assert_eq!(head(&[]), None);
    }

    #[test]
    fn test_tail() {
        assert_eq!(tail(&[1, 2, 3]), Some([2, 3].as_slice()));
        assert_eq!(tail(&[]), None);
    }

    #[test]
    fn test_length() {
        assert_eq!(length(&[1, 2, 3]), 3);
        assert_eq!(length(&[]), 0);
    }

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

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

    #[test]
    fn test_rec_length() {
        assert_eq!(rec_length(&[1, 2, 3, 4]), 4);
    }

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

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

(* 002: List Operations *)
(* Core list operations: head, tail, length, append, reverse *)

(* Approach 1: Standard library *)
let head_of lst = List.hd lst
let tail_of lst = List.tl lst
let length_of lst = List.length lst
let append_lists a b = a @ b
let reverse_list lst = List.rev lst

(* Approach 2: Pattern matching — safer *)
let safe_head = function
  | [] -> None
  | x :: _ -> Some x

let safe_tail = function
  | [] -> None
  | _ :: xs -> Some xs

let rec my_length = function
  | [] -> 0
  | _ :: xs -> 1 + my_length xs

let rec my_append a b =
  match a with
  | [] -> b
  | x :: xs -> x :: my_append xs b

let rec my_reverse = function
  | [] -> []
  | x :: xs -> my_reverse xs @ [x]

(* Approach 3: Tail-recursive reverse *)
let rev_tr lst =
  let rec aux acc = function
    | [] -> acc
    | x :: xs -> aux (x :: acc) xs
  in
  aux [] lst

(* Tests *)
let () =
  assert (head_of [1; 2; 3] = 1);
  assert (tail_of [1; 2; 3] = [2; 3]);
  assert (length_of [1; 2; 3] = 3);
  assert (append_lists [1; 2] [3; 4] = [1; 2; 3; 4]);
  assert (reverse_list [1; 2; 3] = [3; 2; 1]);
  assert (safe_head [] = None);
  assert (safe_head [42] = Some 42);
  assert (safe_tail [] = None);
  assert (my_length [1; 2; 3; 4] = 4);
  assert (my_append [1] [2; 3] = [1; 2; 3]);
  assert (my_reverse [1; 2; 3] = [3; 2; 1]);
  assert (rev_tr [1; 2; 3] = [3; 2; 1]);
  Printf.printf "✓ All tests passed\n"

Key Differences

Stack safety: OCaml guarantees tail-call optimization (TCO); Rust does not. Large recursive functions in Rust require manual conversion to loops or use of fold.

Nil representation: OCaml's [] is a built-in list constructor. Rust uses Vec (heap-allocated) or slices; there is no built-in singly-linked list in the standard library.

Pattern matching: OCaml matches | [] -> ... | x :: t -> ... directly. Rust uses v.split_first() or matches on slice patterns [head, tail @ ..].

Reverse complexity: Both languages have O(n) reverse with an accumulator. Naive recursive reverse (building the result via append on the way back up) is O(n²) in both.

Mutation: Rust can reverse a Vec in-place with v.reverse() — no allocation. OCaml lists are immutable; every "modification" produces a new list. This immutability is what makes OCaml code easy to reason about, but it means garbage collection bears the cost of intermediate structures.

Length caching: Rust's Vec caches its length as a usize field, so .len() is O(1). OCaml's List.length is O(n) — it must walk the entire list.

Structural sharing in OCaml: OCaml's @ operator shares the right list — the second argument is not copied, only the left argument is reconstructed. Rust's extend_from_slice always copies all elements from both sides.

OCaml Approach

OCaml's list operations use pattern matching on the x :: rest constructor. let rec length = function [] -> 0 | _ :: t -> 1 + length t is the canonical recursive form. The tail-recursive version uses an explicit accumulator: let rec length_aux acc = function [] -> acc | _ :: t -> length_aux (acc + 1) t. OCaml does guarantee tail-call optimization, so this form is safe for large lists.

OCaml's standard library (List module) provides all these operations but they operate on singly-linked lists. List.rev uses an accumulator internally: let rec rev_append l acc = match l with [] -> acc | h :: t -> rev_append t (h :: acc). The List.append operator @ is O(|left|) because it must copy the entire left list — appending to the back of a linked list always requires traversal.

Full Source

#![allow(clippy::all)]
// 002: List Operations
// Core list operations: head, tail, length, append, reverse

// Approach 1: Vec methods
fn head(v: &[i32]) -> Option<&i32> {
    v.first()
}

fn tail(v: &[i32]) -> Option<&[i32]> {
    if v.is_empty() {
        None
    } else {
        Some(&v[1..])
    }
}

fn length(v: &[i32]) -> usize {
    v.len()
}

fn append(a: &[i32], b: &[i32]) -> Vec<i32> {
    let mut result = a.to_vec();
    result.extend_from_slice(b);
    result
}

fn reverse(v: &[i32]) -> Vec<i32> {
    v.iter().rev().copied().collect()
}

// Approach 2: Recursive (functional style)
fn rec_length(v: &[i32]) -> usize {
    if v.is_empty() {
        0
    } else {
        1 + rec_length(&v[1..])
    }
}

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

// Approach 3: Tail-recursive with accumulator
fn rev_acc(v: &[i32]) -> Vec<i32> {
    fn aux(slice: &[i32], acc: Vec<i32>) -> Vec<i32> {
        if slice.is_empty() {
            acc
        } else {
            let mut new_acc = vec![slice[0]];
            new_acc.extend(acc);
            aux(&slice[1..], new_acc)
        }
    }
    aux(v, vec![])
}

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

    #[test]
    fn test_head() {
        assert_eq!(head(&[1, 2, 3]), Some(&1));
        assert_eq!(head(&[]), None);
    }

    #[test]
    fn test_tail() {
        assert_eq!(tail(&[1, 2, 3]), Some([2, 3].as_slice()));
        assert_eq!(tail(&[]), None);
    }

    #[test]
    fn test_length() {
        assert_eq!(length(&[1, 2, 3]), 3);
        assert_eq!(length(&[]), 0);
    }

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

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

    #[test]
    fn test_rec_length() {
        assert_eq!(rec_length(&[1, 2, 3, 4]), 4);
    }

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

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

(* 002: List Operations *)
(* Core list operations: head, tail, length, append, reverse *)

(* Approach 1: Standard library *)
let head_of lst = List.hd lst
let tail_of lst = List.tl lst
let length_of lst = List.length lst
let append_lists a b = a @ b
let reverse_list lst = List.rev lst

(* Approach 2: Pattern matching — safer *)
let safe_head = function
  | [] -> None
  | x :: _ -> Some x

let safe_tail = function
  | [] -> None
  | _ :: xs -> Some xs

let rec my_length = function
  | [] -> 0
  | _ :: xs -> 1 + my_length xs

let rec my_append a b =
  match a with
  | [] -> b
  | x :: xs -> x :: my_append xs b

let rec my_reverse = function
  | [] -> []
  | x :: xs -> my_reverse xs @ [x]

(* Approach 3: Tail-recursive reverse *)
let rev_tr lst =
  let rec aux acc = function
    | [] -> acc
    | x :: xs -> aux (x :: acc) xs
  in
  aux [] lst

(* Tests *)
let () =
  assert (head_of [1; 2; 3] = 1);
  assert (tail_of [1; 2; 3] = [2; 3]);
  assert (length_of [1; 2; 3] = 3);
  assert (append_lists [1; 2] [3; 4] = [1; 2; 3; 4]);
  assert (reverse_list [1; 2; 3] = [3; 2; 1]);
  assert (safe_head [] = None);
  assert (safe_head [42] = Some 42);
  assert (safe_tail [] = None);
  assert (my_length [1; 2; 3; 4] = 4);
  assert (my_append [1] [2; 3] = [1; 2; 3]);
  assert (my_reverse [1; 2; 3] = [3; 2; 1]);
  assert (rev_tr [1; 2; 3] = [3; 2; 1]);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_head() {
        assert_eq!(head(&[1, 2, 3]), Some(&1));
        assert_eq!(head(&[]), None);
    }

    #[test]
    fn test_tail() {
        assert_eq!(tail(&[1, 2, 3]), Some([2, 3].as_slice()));
        assert_eq!(tail(&[]), None);
    }

    #[test]
    fn test_length() {
        assert_eq!(length(&[1, 2, 3]), 3);
        assert_eq!(length(&[]), 0);
    }

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

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

    #[test]
    fn test_rec_length() {
        assert_eq!(rec_length(&[1, 2, 3, 4]), 4);
    }

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

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

Deep Comparison

Core Insight

OCaml's list is an immutable singly-linked list (O(1) prepend, O(n) append). Rust's Vec<T> is a contiguous growable array (O(1) push to end, O(n) insert at front). This fundamental difference shapes idiomatic usage.

OCaml Approach

• List.hd / List.tl for head/tail (raise exception on empty)

• List.length counts nodes — O(n)

• @ or List.append for concatenation — O(n) in first list

• List.rev for reverse — O(n)

• Pattern matching preferred over hd/tl

Rust Approach

• .first() / .last() return Option<&T>

• .len() is O(1) — stored metadata

• .extend() or [a, b].concat() for append

• .reverse() in-place or .iter().rev().collect()

• Slices &[T] for borrowing sub-ranges

Comparison Table

Operation	OCaml	Rust Vec
Head	`List.hd` / pattern match	`.first()` → `Option`
Tail	`List.tl`	`&v[1..]` slice
Length	`List.length` O(n)	`.len()` O(1)
Prepend	`x :: lst` O(1)	`.insert(0, x)` O(n)
Append	`lst @ [x]` O(n)	`.push(x)` O(1) amortized
Reverse	`List.rev`	`.reverse()` in-place

Exercises

Last element: Write last(v: &[i32]) -> Option<i32> that returns the last element, implemented both with .last() and with tail-recursive decomposition.

Flatten: Write flatten(vecs: &[Vec<i32>]) -> Vec<i32> that concatenates all inner lists into one, using iter().flatten().collect() and a manual fold-based version.

Zip: Write zip(a: &[i32], b: &[i32]) -> Vec<(i32, i32)> that pairs elements position-by-position, stopping at the shorter list, using .zip() and then recursively.

Interleave: Write interleave(a: &[i32], b: &[i32]) -> Vec<i32> that alternates elements from two lists: [1,2,3] + [a,b,c] → [1,a,2,b,3,c]. Stop at the shorter list.

Take and drop: Implement take(n, v: &[i32]) -> Vec<i32> and drop(n, v: &[i32]) -> Vec<i32> using slice patterns and iterators.

Open Source Repos

functional-rust

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

Rust