114 Intermediate

114-slice-patterns — Slice Patterns

Functional Programming

Tutorial

The Problem

Pattern matching on sequences is the heart of functional programming. OCaml's list patterns x :: rest enable recursive algorithms that read naturally. Rust provides analogous slice patterns — [first, rest @ ..], [a, b], [head, .., tail] — for contiguous memory. Unlike OCaml's linked lists, Rust's slice patterns operate on contiguous arrays with O(1) indexed access.

Slice patterns enable writing recursive algorithms in a functional style that the compiler verifies for exhaustiveness, bringing OCaml-style list processing to Rust's arrays and slices.

🎯 Learning Outcomes

• Use [head, rest @ ..] to deconstruct a slice like OCaml's x :: rest

• Match fixed-length slices with [a, b], [a, b, c]

• Use [first, .., last] to bind first and last without naming the middle

• Write recursive functions using slice patterns

• Understand exhaustiveness checking for slice patterns

Code Example

// Iterator-based — idiomatic for contiguous memory
pub fn sum_idiomatic(slice: &[i32]) -> i32 {
    slice.iter().sum()
}

pub fn is_sorted_asc_idiomatic(slice: &[i32]) -> bool {
    slice.windows(2).all(|w| w[0] <= w[1])
}

(* Head/tail destructuring on linked lists *)
let rec sum = function
  | [] -> 0
  | x :: rest -> x + sum rest

let describe = function
  | [] -> "empty"
  | [_] -> "singleton"
  | [_; _] -> "pair"
  | _ :: _ :: _ -> "many"

Key Differences

Contiguous vs linked: Rust's [head, rest @ ..] binds a contiguous subslice (a reference, zero cost); OCaml's x :: rest binds the next node in a linked list.

Rest binding: Rust's rest @ .. is a slice reference — no copying; OCaml's rest in x :: rest is the tail list (shared immutable structure).

Exhaustiveness: Both compilers check exhaustiveness for slice/list patterns; Rust reports missing cases for fixed-length patterns.

OCaml array patterns: [| a; b; c |] matches OCaml arrays; Rust's [a, b, c] matches Rust slices of length 3 — semantically equivalent.

OCaml Approach

OCaml's list patterns are the original inspiration:

let rec sum = function
  | [] -> 0
  | x :: rest -> x + sum rest

let describe = function
  | [] -> "empty"
  | [_] -> "singleton"
  | [_; _] -> "pair"
  | _ -> "many"

OCaml's list patterns operate on linked lists; Rust's slice patterns operate on contiguous memory. OCaml 4.12+ also supports array patterns with [| a; b |] syntax.

Full Source

#![allow(clippy::all)]
// Example 114: Slice Patterns
//
// Rust can pattern match on slices: [first, rest @ ..], [a, b], [head, .., tail]
// Similar to OCaml's list patterns but on contiguous memory with exhaustiveness checking.

// --- Approach 1: Recursive sum and take using head/tail patterns ---

/// Sum all elements recursively, mirroring OCaml's `| x :: rest -> x + sum rest`.
pub fn sum(slice: &[i32]) -> i32 {
    match slice {
        [] => 0,
        [x, rest @ ..] => x + sum(rest),
    }
}

/// Take the first `n` elements, returning a new Vec.
pub fn take(n: usize, slice: &[i32]) -> Vec<i32> {
    match (n, slice) {
        (0, _) | (_, []) => vec![],
        (_, [x, rest @ ..]) => {
            let mut result = vec![*x];
            result.extend(take(n - 1, rest));
            result
        }
    }
}

// --- Approach 2: Structural shape matching ---

/// Describe the shape of a slice.
pub fn describe(slice: &[i32]) -> &'static str {
    match slice {
        [] => "empty",
        [_] => "singleton",
        [_, _] => "pair",
        _ => "many",
    }
}

/// Return the first and last elements, if they exist.
pub fn first_and_last(slice: &[i32]) -> Option<(i32, i32)> {
    match slice {
        [] => None,
        [only] => Some((*only, *only)),
        [head, .., tail] => Some((*head, *tail)),
    }
}

// --- Approach 3: Idiomatic iterator-based alternatives ---

/// Idiomatic Rust: sum with `.sum()`.
pub fn sum_idiomatic(slice: &[i32]) -> i32 {
    slice.iter().sum()
}

/// Idiomatic Rust: take with `.take()`.
pub fn take_idiomatic(n: usize, slice: &[i32]) -> Vec<i32> {
    slice.iter().copied().take(n).collect()
}

/// Detect if a slice is sorted ascending — recursive with slice patterns.
/// Matches [a, b, ..] then recurses on the tail slice.
pub fn is_sorted_asc(slice: &[i32]) -> bool {
    match slice {
        [] | [_] => true,
        [a, b, ..] => a <= b && is_sorted_asc(&slice[1..]),
    }
}

/// Idiomatic alternative: sorted check with `.windows(2)`.
pub fn is_sorted_asc_idiomatic(slice: &[i32]) -> bool {
    slice.windows(2).all(|w| w[0] <= w[1])
}

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

    // --- sum ---
    #[test]
    fn test_sum_empty() {
        assert_eq!(sum(&[]), 0);
    }

    #[test]
    fn test_sum_single() {
        assert_eq!(sum(&[42]), 42);
    }

    #[test]
    fn test_sum_multiple() {
        assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
    }

    #[test]
    fn test_sum_matches_idiomatic() {
        let data = [10, 20, 30];
        assert_eq!(sum(&data), sum_idiomatic(&data));
    }

    // --- take ---
    #[test]
    fn test_take_zero() {
        assert_eq!(take(0, &[1, 2, 3]), vec![]);
    }

    #[test]
    fn test_take_fewer_than_available() {
        assert_eq!(take(3, &[1, 2, 3, 4, 5]), vec![1, 2, 3]);
    }

    #[test]
    fn test_take_more_than_available() {
        assert_eq!(take(10, &[1, 2]), vec![1, 2]);
    }

    #[test]
    fn test_take_matches_idiomatic() {
        let data = [1, 2, 3, 4, 5];
        assert_eq!(take(3, &data), take_idiomatic(3, &data));
    }

    // --- describe ---
    #[test]
    fn test_describe_empty() {
        assert_eq!(describe(&[]), "empty");
    }

    #[test]
    fn test_describe_singleton() {
        assert_eq!(describe(&[99]), "singleton");
    }

    #[test]
    fn test_describe_pair() {
        assert_eq!(describe(&[1, 2]), "pair");
    }

    #[test]
    fn test_describe_many() {
        assert_eq!(describe(&[1, 2, 3]), "many");
        assert_eq!(describe(&[1, 2, 3, 4, 5]), "many");
    }

    // --- first_and_last ---
    #[test]
    fn test_first_and_last_empty() {
        assert_eq!(first_and_last(&[]), None);
    }

    #[test]
    fn test_first_and_last_single() {
        assert_eq!(first_and_last(&[7]), Some((7, 7)));
    }

    #[test]
    fn test_first_and_last_multiple() {
        assert_eq!(first_and_last(&[1, 2, 3, 4, 5]), Some((1, 5)));
    }

    #[test]
    fn test_first_and_last_pair() {
        assert_eq!(first_and_last(&[3, 9]), Some((3, 9)));
    }

    // --- is_sorted_asc ---
    #[test]
    fn test_sorted_empty() {
        assert!(is_sorted_asc(&[]));
        assert!(is_sorted_asc_idiomatic(&[]));
    }

    #[test]
    fn test_sorted_ascending() {
        assert!(is_sorted_asc(&[1, 2, 3, 4]));
        assert!(is_sorted_asc_idiomatic(&[1, 2, 3, 4]));
    }

    #[test]
    fn test_not_sorted() {
        assert!(!is_sorted_asc(&[1, 3, 2, 4]));
        assert!(!is_sorted_asc_idiomatic(&[1, 3, 2, 4]));
    }

    #[test]
    fn test_sorted_equal_elements() {
        assert!(is_sorted_asc(&[5, 5, 5]));
        assert!(is_sorted_asc_idiomatic(&[5, 5, 5]));
    }
}

(* Example 114: Slice Patterns — OCaml List Pattern Matching in Rust *)

(* Approach 1: Head/tail pattern matching *)
let rec sum = function
  | [] -> 0
  | x :: rest -> x + sum rest

let rec take n = function
  | _ when n <= 0 -> []
  | [] -> []
  | x :: rest -> x :: take (n - 1) rest

let approach1 () =
  assert (sum [1; 2; 3; 4; 5] = 15);
  assert (take 3 [1; 2; 3; 4; 5] = [1; 2; 3]);
  Printf.printf "Sum: %d, Take 3: %s\n" (sum [1;2;3;4;5])
    (String.concat "," (List.map string_of_int (take 3 [1;2;3;4;5])))

(* Approach 2: Matching specific patterns *)
let describe = function
  | [] -> "empty"
  | [_] -> "singleton"
  | [_; _] -> "pair"
  | _ :: _ :: _ -> "many"

let approach2 () =
  assert (describe [] = "empty");
  assert (describe [1] = "singleton");
  assert (describe [1; 2] = "pair");
  assert (describe [1; 2; 3] = "many");
  Printf.printf "Patterns work!\n"

(* Approach 3: First, last, and middle *)
let first_and_last lst =
  match lst with
  | [] -> None
  | [x] -> Some (x, x)
  | x :: rest ->
    let last = List.nth rest (List.length rest - 1) in
    Some (x, last)

let approach3 () =
  assert (first_and_last [] = None);
  assert (first_and_last [1] = Some (1, 1));
  assert (first_and_last [1; 2; 3] = Some (1, 3));
  Printf.printf "First and last work!\n"

let () =
  approach1 ();
  approach2 ();
  approach3 ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    // --- sum ---
    #[test]
    fn test_sum_empty() {
        assert_eq!(sum(&[]), 0);
    }

    #[test]
    fn test_sum_single() {
        assert_eq!(sum(&[42]), 42);
    }

    #[test]
    fn test_sum_multiple() {
        assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
    }

    #[test]
    fn test_sum_matches_idiomatic() {
        let data = [10, 20, 30];
        assert_eq!(sum(&data), sum_idiomatic(&data));
    }

    // --- take ---
    #[test]
    fn test_take_zero() {
        assert_eq!(take(0, &[1, 2, 3]), vec![]);
    }

    #[test]
    fn test_take_fewer_than_available() {
        assert_eq!(take(3, &[1, 2, 3, 4, 5]), vec![1, 2, 3]);
    }

    #[test]
    fn test_take_more_than_available() {
        assert_eq!(take(10, &[1, 2]), vec![1, 2]);
    }

    #[test]
    fn test_take_matches_idiomatic() {
        let data = [1, 2, 3, 4, 5];
        assert_eq!(take(3, &data), take_idiomatic(3, &data));
    }

    // --- describe ---
    #[test]
    fn test_describe_empty() {
        assert_eq!(describe(&[]), "empty");
    }

    #[test]
    fn test_describe_singleton() {
        assert_eq!(describe(&[99]), "singleton");
    }

    #[test]
    fn test_describe_pair() {
        assert_eq!(describe(&[1, 2]), "pair");
    }

    #[test]
    fn test_describe_many() {
        assert_eq!(describe(&[1, 2, 3]), "many");
        assert_eq!(describe(&[1, 2, 3, 4, 5]), "many");
    }

    // --- first_and_last ---
    #[test]
    fn test_first_and_last_empty() {
        assert_eq!(first_and_last(&[]), None);
    }

    #[test]
    fn test_first_and_last_single() {
        assert_eq!(first_and_last(&[7]), Some((7, 7)));
    }

    #[test]
    fn test_first_and_last_multiple() {
        assert_eq!(first_and_last(&[1, 2, 3, 4, 5]), Some((1, 5)));
    }

    #[test]
    fn test_first_and_last_pair() {
        assert_eq!(first_and_last(&[3, 9]), Some((3, 9)));
    }

    // --- is_sorted_asc ---
    #[test]
    fn test_sorted_empty() {
        assert!(is_sorted_asc(&[]));
        assert!(is_sorted_asc_idiomatic(&[]));
    }

    #[test]
    fn test_sorted_ascending() {
        assert!(is_sorted_asc(&[1, 2, 3, 4]));
        assert!(is_sorted_asc_idiomatic(&[1, 2, 3, 4]));
    }

    #[test]
    fn test_not_sorted() {
        assert!(!is_sorted_asc(&[1, 3, 2, 4]));
        assert!(!is_sorted_asc_idiomatic(&[1, 3, 2, 4]));
    }

    #[test]
    fn test_sorted_equal_elements() {
        assert!(is_sorted_asc(&[5, 5, 5]));
        assert!(is_sorted_asc_idiomatic(&[5, 5, 5]));
    }
}

Deep Comparison

OCaml vs Rust: Slice Patterns

Side-by-Side Code

OCaml

(* Head/tail destructuring on linked lists *)
let rec sum = function
  | [] -> 0
  | x :: rest -> x + sum rest

let describe = function
  | [] -> "empty"
  | [_] -> "singleton"
  | [_; _] -> "pair"
  | _ :: _ :: _ -> "many"

Rust (idiomatic)

// Iterator-based — idiomatic for contiguous memory
pub fn sum_idiomatic(slice: &[i32]) -> i32 {
    slice.iter().sum()
}

pub fn is_sorted_asc_idiomatic(slice: &[i32]) -> bool {
    slice.windows(2).all(|w| w[0] <= w[1])
}

Rust (functional/recursive — slice patterns)

// Structural match on slice shape — mirrors OCaml list patterns
pub fn sum(slice: &[i32]) -> i32 {
    match slice {
        [] => 0,
        [x, rest @ ..] => x + sum(rest),
    }
}

pub fn first_and_last(slice: &[i32]) -> Option<(i32, i32)> {
    match slice {
        [] => None,
        [only] => Some((*only, *only)),
        [head, .., tail] => Some((*head, *tail)),
    }
}

Type Signatures

Concept	OCaml	Rust
Recursive sum	`val sum : int list -> int`	`fn sum(slice: &[i32]) -> i32`
Head/tail pattern	`x :: rest`	`[x, rest @ ..]`
Empty pattern	`[]`	`[]`
Singleton pattern	`[x]`	`[x]`
First and last	`List.hd`, `List.rev \\|> List.hd`	`[head, .., tail]` (one match arm)
List type	`'a list` (linked list)	`&[T]` (contiguous slice)

Key Insights

Memory model: OCaml's :: patterns work on singly-linked lists with O(1) head access. Rust's slice patterns work on contiguous memory — a fundamentally different layout that enables cache-friendly traversal.

**The rest @ .. binding**: rest @ .. in Rust captures the remainder of the slice as a &[T] — the @ binds a name to the matched segment. OCaml's rest in x :: rest is just a variable bound to the tail list. Both give you "everything after the head", but Rust's tail is a slice reference, not a new allocation.

**[head, .., tail] has no OCaml equivalent**: Matching on both the first and last element simultaneously requires an explicit list traversal in OCaml. Rust's .. skip pattern does it in one arm with no extra allocation, exploiting random-access into the slice.

Exhaustiveness at compile time: Both OCaml and Rust compilers check that all cases are covered. Missing a [] arm is a compile error in both. In Rust this extends to numeric ranges and struct fields — the same principle, broader application.

When to prefer each style: The recursive slice-pattern style mirrors OCaml thinking and is readable for algorithms naturally expressed as "head + tail". The idiomatic iterator style (.sum(), .windows(2)) compiles to tighter loops and should be preferred when the standard library already has the operation.

When to Use Each Style

Use idiomatic Rust (iterators) when: the operation maps cleanly to .sum(), .take(), .windows(), .zip() or other iterator adapters — these compile to tight loops with no recursion overhead.

Use recursive slice patterns when: the algorithm is naturally recursive (e.g., merge sort, parsing, tree-shaped data embedded in slices), or when you want to make the OCaml parallel explicit for teaching purposes.

Exercises

Write merge_sorted(a: &[i32], b: &[i32]) -> Vec<i32> using slice patterns to implement the merge step of merge sort.

Implement run_length_encode(s: &[i32]) -> Vec<(i32, usize)> using slice patterns to detect runs of equal elements.

Write a simple expression parser using slice patterns to match token sequences like [Num(n), Plus, Num(m)].

Open Source Repos

functional-rust

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

Rust