004 Fundamental

List Length

ListsRecursion

Tutorial Video

Text description (accessibility)

This video demonstrates the "List Length" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Lists, Recursion. Compute the number of elements in a list. Key difference from OCaml: 1. **Complexity:** Rust `.len()` is O(1) — the length is stored with the slice; OCaml lists require O(n) traversal

Tutorial

The Problem

Compute the number of elements in a list. OCaml demonstrates naive recursion vs tail-recursive accumulator.

Computing the length of a sequence is so fundamental that most languages cache it. Rust's Vec<T> and slice &[T] store a usize length alongside the data pointer, making .len() O(1) and infallible. This contrasts sharply with OCaml's linked lists, where length requires O(n) traversal. Understanding this trade-off — list flexibility vs array length caching — is essential for choosing the right data structure.

🎯 Learning Outcomes

• Understanding O(1) .len() on Rust slices vs O(n) in OCaml

• Tail recursion and why Rust doesn't guarantee TCO

• fold as the functional accumulator pattern

• Stack overflow risks with naive recursion

• How data structure choice (array vs linked list) fundamentally changes complexity

🦀 The Rust Way

.len() is trivially O(1) since slices store their length. For educational purposes, we also implement fold-based and recursive versions matching the OCaml patterns.

Code Example

pub fn length<T>(slice: &[T]) -> usize {
    slice.len()  // O(1) — stored metadata
}

let rec length_naive = function
  | [] -> 0
  | _ :: t -> 1 + length_naive t

Key Differences

Complexity: Rust .len() is O(1) — the length is stored with the slice; OCaml lists require O(n) traversal

TCO: OCaml guarantees tail-call optimization; Rust does not — tail-recursive Rust code can still overflow

Fold: Rust's fold is iterative (no stack growth); OCaml's List.fold_left is tail-recursive — same safety guarantees

Practical value: In Rust, manual length computation is purely educational; in OCaml, the tail-recursive version matters

Large lists: OCaml's naive version risks stack overflow; Rust's naive version does too, but .len() eliminates the need

Complexity: slice.len() is O(1) — the length is stored alongside the data. List.length in OCaml is O(n) — the list must be traversed. This alone makes arrays preferable for length-sensitive operations.

Stack safety: OCaml guarantees tail-call optimization, so the accumulator-based length_aux is safe for arbitrarily long lists. Rust does not guarantee TCO; the recursive version will stack-overflow on lists longer than ~10,000 elements.

Type: Rust .len() returns usize (unsigned). OCaml List.length returns int (signed). Rust's choice avoids negative-length bugs at the type level.

OCaml Approach

Two implementations: naive 1 + length_naive t (stack risk) and tail-recursive aux n with accumulator. The tail-recursive version is production-ready in OCaml.

OCaml's List.length : 'a list -> int is O(n) and non-tail-recursive in older versions. The standard library now uses the tail-recursive form internally. For large lists, always prefer the tail-recursive version: let rec aux acc = function [] -> acc | _ :: t -> aux (acc + 1) t. Calling List.length in a tight loop on long lists has been a real performance footgun in OCaml codebases.

Full Source

#![allow(clippy::all)]
// Compute the length of a list. OCaml shows naive vs tail-recursive versions.
// In Rust, `.len()` is O(1) for slices/Vec — but we implement manual versions
// for educational comparison.

// ---------------------------------------------------------------------------
// Approach 1: Idiomatic Rust — .len() (O(1) for slices)
// ---------------------------------------------------------------------------
// Slices store their length alongside the pointer, so this is trivial.
pub fn length<T>(slice: &[T]) -> usize {
    slice.len()
}

// ---------------------------------------------------------------------------
// Approach 2: Fold — functional accumulator pattern
// ---------------------------------------------------------------------------
// Mirrors OCaml's tail-recursive `aux n = function` with an explicit fold.
pub fn length_fold<T>(slice: &[T]) -> usize {
    // fold is inherently iterative in Rust (no stack growth)
    slice.iter().fold(0, |acc, _| acc + 1)
}

// ---------------------------------------------------------------------------
// Approach 3: Recursive — mirrors OCaml's naive version
// ---------------------------------------------------------------------------
// Educational only: Rust doesn't guarantee TCO, and slices make this awkward.
pub fn length_recursive<T>(slice: &[T]) -> usize {
    match slice {
        [] => 0,
        [_, rest @ ..] => 1 + length_recursive(rest),
    }
}

// ---------------------------------------------------------------------------
// Approach 4: Tail-recursive style — mirrors OCaml's production version
// ---------------------------------------------------------------------------
pub fn length_tail<T>(slice: &[T]) -> usize {
    fn aux<T>(n: usize, slice: &[T]) -> usize {
        match slice {
            [] => n,
            [_, rest @ ..] => aux(n + 1, rest),
        }
    }
    aux(0, slice)
}

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

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

    #[test]
    fn test_basic() {
        let v = [1, 2, 3, 4];
        assert_eq!(length(&v), 4);
        assert_eq!(length_fold(&v), 4);
        assert_eq!(length_recursive(&v), 4);
        assert_eq!(length_tail(&v), 4);
    }

    #[test]
    fn test_single() {
        assert_eq!(length(&[42]), 1);
        assert_eq!(length_fold(&[42]), 1);
    }

    #[test]
    fn test_large() {
        let v: Vec<i32> = (0..10000).collect();
        assert_eq!(length(&v), 10000);
        assert_eq!(length_fold(&v), 10000);
        // Skip recursive for large — may stack overflow
    }

    #[test]
    fn test_strings() {
        let v = ["hello", "world", "foo"];
        assert_eq!(length(&v), 3);
    }
}

(* Find the length of a list *)

(* Naive recursion (stack overflow risk) *)
let rec length_naive = function
  | [] -> 0
  | _ :: t -> 1 + length_naive t

(* Tail-recursive (production-ready) *)
let length list =
  let rec aux n = function
    | [] -> n
    | _ :: t -> aux (n + 1) t
  in
  aux 0 list

(* Tests *)
let () =
  assert (length [] = 0);
  assert (length [1; 2; 3; 4] = 4);
  assert (length (List.init 10000 (fun x -> x)) = 10000);
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

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

    #[test]
    fn test_basic() {
        let v = [1, 2, 3, 4];
        assert_eq!(length(&v), 4);
        assert_eq!(length_fold(&v), 4);
        assert_eq!(length_recursive(&v), 4);
        assert_eq!(length_tail(&v), 4);
    }

    #[test]
    fn test_single() {
        assert_eq!(length(&[42]), 1);
        assert_eq!(length_fold(&[42]), 1);
    }

    #[test]
    fn test_large() {
        let v: Vec<i32> = (0..10000).collect();
        assert_eq!(length(&v), 10000);
        assert_eq!(length_fold(&v), 10000);
        // Skip recursive for large — may stack overflow
    }

    #[test]
    fn test_strings() {
        let v = ["hello", "world", "foo"];
        assert_eq!(length(&v), 3);
    }
}

Deep Comparison

Comparison: List Length

OCaml — Naive

let rec length_naive = function
  | [] -> 0
  | _ :: t -> 1 + length_naive t

OCaml — Tail-recursive

let length list =
  let rec aux n = function
    | [] -> n
    | _ :: t -> aux (n + 1) t
  in aux 0 list

Rust — Idiomatic

pub fn length<T>(slice: &[T]) -> usize {
    slice.len()  // O(1) — stored metadata
}

Rust — Fold

pub fn length_fold<T>(slice: &[T]) -> usize {
    slice.iter().fold(0, |acc, _| acc + 1)
}

Rust — Recursive (naive)

pub fn length_recursive<T>(slice: &[T]) -> usize {
    match slice {
        [] => 0,
        [_, rest @ ..] => 1 + length_recursive(rest),
    }
}

Rust — Tail-recursive style

pub fn length_tail<T>(slice: &[T]) -> usize {
    fn aux<T>(n: usize, slice: &[T]) -> usize {
        match slice {
            [] => n,
            [_, rest @ ..] => aux(n + 1, rest),
        }
    }
    aux(0, slice)
}

Comparison Table

Aspect	OCaml	Rust
Best approach	`List.length` or tail-recursive	`.len()` (O(1))
Data structure	Linked list (no stored length)	Slice (fat pointer with length)
TCO	Guaranteed	Not guaranteed
Naive recursion	Stack overflow on large lists	Same risk
Fold	`List.fold_left` (tail-recursive)	`.fold()` (iterative)

Type Signatures

• OCaml: val length : 'a list -> int

• Rust: fn length<T>(slice: &[T]) -> usize

Takeaways

Data structure choice dominates: slices carry their length; linked lists don't — this single difference makes the entire problem trivial in Rust

OCaml's TCO guarantee makes tail recursion a real optimization tool; in Rust, prefer iterators/fold instead

fold is the universal functional accumulator — same pattern in both languages, same safety

Rust's usize vs OCaml's int: unsigned vs signed return types for inherently non-negative values

The educational value is in seeing why the problem exists in OCaml (linked lists) and why it doesn't in Rust (slices)

Exercises

Implement list_length without using .len() or .count() — use only a fold or manual recursion.

Write length_bounded that counts elements up to a maximum limit, stopping early once the limit is reached (without scanning the rest of the list).

Implement lengths that takes a Vec<Vec<T>> and returns a Vec<usize> containing the length of each inner list, using only iterator combinators.

Open Source Repos

functional-rust

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

Rust