271 Intermediate

Sublist Classification

ListsHOFPattern Matching

Tutorial Video

Text description (accessibility)

This video demonstrates the "Sublist Classification" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Lists, HOF, Pattern Matching. Given two lists, classify their relationship: one list is equal to, a sublist of, a superlist of, or completely unequal to the other. Key difference from OCaml: 1. **List walking:** OCaml recurses on `h :: t`; Rust iterates via `.windows()` or uses slice patterns

Tutorial

The Problem

Given two lists, classify their relationship: one list is equal to, a sublist of, a superlist of, or completely unequal to the other.

🎯 Learning Outcomes

• How slice::windows enables elegant contiguous subsequence searching

• How slice pattern matching ([h, rest @ ..]) mirrors OCaml's h :: t destructuring

• The idiomatic Rust approach to replacing recursive list walks with iterator combinators

• How a sum type (enum) maps directly from OCaml's variant type to Rust

🦀 The Rust Way

The idiomatic Rust solution uses slice::windows(n) to generate all contiguous sub-slices of length n and checks if any equals the target — a single iterator expression replaces the recursive walk. The recursive solution preserves the OCaml structure exactly using slice patterns with rest bindings ([h, rest @ ..]).

Code Example

pub fn classify_idiomatic<T: PartialEq>(a: &[T], b: &[T]) -> Relation {
    if a == b {
        Relation::Equal
    } else if is_sublist_idiomatic(a, b) {
        Relation::Sublist
    } else if is_sublist_idiomatic(b, a) {
        Relation::Superlist
    } else {
        Relation::Unequal
    }
}

fn is_sublist_idiomatic<T: PartialEq>(sub: &[T], lst: &[T]) -> bool {
    if sub.is_empty() { return true; }
    lst.windows(sub.len()).any(|w| w == sub)
}

type relation = Equal | Sublist | Superlist | Unequal

let rec starts_with lst prefix = match lst, prefix with
  | _, [] -> true
  | [], _ -> false
  | h1 :: t1, h2 :: t2 -> h1 = h2 && starts_with t1 t2

let rec is_sublist sub lst = match lst with
  | [] -> sub = []
  | _ :: t -> starts_with lst sub || is_sublist sub t

let classify a b =
  if a = b then Equal
  else if is_sublist a b then Sublist
  else if is_sublist b a then Superlist
  else Unequal

Key Differences

List walking: OCaml recurses on h :: t; Rust iterates via .windows() or uses slice patterns

Equality: OCaml's structural = works on lists; Rust requires PartialEq bound on the generic T

Empty check: OCaml matches sub = []; Rust uses sub.is_empty()

Type: OCaml type relation = ... is a sum type; Rust enum Relation is identical in concept

OCaml Approach

OCaml defines a recursive starts_with helper and is_sublist that walks the list head-by-head, checking at every position whether the prefix matches. The classify function then uses equality (=) as a structural check before delegating to the sublist tests.

Full Source

#![allow(clippy::all)]
//! Sublist classification: determine whether two lists are equal,
//! one is a sublist of the other, or they are unequal.

#[derive(Debug, PartialEq, Eq)]
pub enum Relation {
    Equal,
    Sublist,
    Superlist,
    Unequal,
}

// Solution 1: Idiomatic Rust — uses slice windows for contiguous sublist check
pub fn classify_idiomatic<T: PartialEq>(a: &[T], b: &[T]) -> Relation {
    if a == b {
        Relation::Equal
    } else if is_sublist_idiomatic(a, b) {
        Relation::Sublist
    } else if is_sublist_idiomatic(b, a) {
        Relation::Superlist
    } else {
        Relation::Unequal
    }
}

// Returns true if `sub` appears as a contiguous subslice anywhere in `lst`
fn is_sublist_idiomatic<T: PartialEq>(sub: &[T], lst: &[T]) -> bool {
    if sub.is_empty() {
        return true;
    }
    lst.windows(sub.len()).any(|w| w == sub)
}

// Solution 2: Functional/recursive — mirrors the OCaml pattern-match style
pub fn classify_recursive<T: PartialEq>(a: &[T], b: &[T]) -> Relation {
    if a == b {
        Relation::Equal
    } else if is_sublist_recursive(a, b) {
        Relation::Sublist
    } else if is_sublist_recursive(b, a) {
        Relation::Superlist
    } else {
        Relation::Unequal
    }
}

fn starts_with<T: PartialEq>(lst: &[T], prefix: &[T]) -> bool {
    match (lst, prefix) {
        (_, []) => true,
        ([], _) => false,
        ([h1, t1 @ ..], [h2, t2 @ ..]) => h1 == h2 && starts_with(t1, t2),
    }
}

fn is_sublist_recursive<T: PartialEq>(sub: &[T], lst: &[T]) -> bool {
    match lst {
        [] => sub.is_empty(),
        [_, rest @ ..] => starts_with(lst, sub) || is_sublist_recursive(sub, rest),
    }
}

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

    // --- idiomatic ---

    #[test]
    fn test_idiomatic_equal() {
        assert_eq!(classify_idiomatic(&[1, 2, 3], &[1, 2, 3]), Equal);
    }

    #[test]
    fn test_idiomatic_sublist() {
        assert_eq!(classify_idiomatic(&[1, 2, 3], &[0, 1, 2, 3, 4]), Sublist);
    }

    #[test]
    fn test_idiomatic_superlist() {
        assert_eq!(classify_idiomatic(&[0, 1, 2, 3, 4], &[1, 2, 3]), Superlist);
    }

    #[test]
    fn test_idiomatic_unequal() {
        assert_eq!(classify_idiomatic(&[1, 2, 3], &[4, 5, 6]), Unequal);
    }

    #[test]
    fn test_idiomatic_empty_sub_is_sublist() {
        assert_eq!(classify_idiomatic::<i32>(&[], &[1, 2, 3]), Sublist);
    }

    #[test]
    fn test_idiomatic_both_empty_equal() {
        assert_eq!(classify_idiomatic::<i32>(&[], &[]), Equal);
    }

    #[test]
    fn test_idiomatic_non_contiguous_not_sublist() {
        // [1,3] is NOT a contiguous sublist of [1,2,3]
        assert_eq!(classify_idiomatic(&[1, 3], &[1, 2, 3]), Unequal);
    }

    // --- recursive ---

    #[test]
    fn test_recursive_equal() {
        assert_eq!(classify_recursive(&[1, 2, 3], &[1, 2, 3]), Equal);
    }

    #[test]
    fn test_recursive_sublist() {
        assert_eq!(classify_recursive(&[1, 2, 3], &[0, 1, 2, 3, 4]), Sublist);
    }

    #[test]
    fn test_recursive_superlist() {
        assert_eq!(classify_recursive(&[0, 1, 2, 3, 4], &[1, 2, 3]), Superlist);
    }

    #[test]
    fn test_recursive_unequal() {
        assert_eq!(classify_recursive(&[1, 2, 3], &[4, 5, 6]), Unequal);
    }

    #[test]
    fn test_recursive_empty_sub_is_sublist() {
        assert_eq!(classify_recursive::<i32>(&[], &[1, 2, 3]), Sublist);
    }

    #[test]
    fn test_recursive_both_empty_equal() {
        assert_eq!(classify_recursive::<i32>(&[], &[]), Equal);
    }

    #[test]
    fn test_recursive_non_contiguous_not_sublist() {
        assert_eq!(classify_recursive(&[1, 3], &[1, 2, 3]), Unequal);
    }
}

type relation = Equal | Sublist | Superlist | Unequal

(* Idiomatic OCaml: use List.filteri/exists with starts_with *)
let rec starts_with lst prefix = match lst, prefix with
  | _, [] -> true
  | [], _ -> false
  | h1 :: t1, h2 :: t2 -> h1 = h2 && starts_with t1 t2

let rec is_sublist sub lst = match lst with
  | [] -> sub = []
  | _ :: t -> starts_with lst sub || is_sublist sub t

let classify a b =
  if a = b then Equal
  else if is_sublist a b then Sublist
  else if is_sublist b a then Superlist
  else Unequal

let name = function
  | Equal -> "equal" | Sublist -> "sublist"
  | Superlist -> "superlist" | Unequal -> "unequal"

let () =
  assert (classify [1;2;3] [0;1;2;3;4] = Sublist);
  assert (classify [0;1;2;3;4] [1;2;3] = Superlist);
  assert (classify [1;2;3] [1;2;3] = Equal);
  assert (classify [1;2;3] [4;5;6] = Unequal);
  assert (classify [] [1;2;3] = Sublist);
  assert (classify [] [] = Equal);
  print_endline "ok"

✓ Tests Rust test suite

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

    // --- idiomatic ---

    #[test]
    fn test_idiomatic_equal() {
        assert_eq!(classify_idiomatic(&[1, 2, 3], &[1, 2, 3]), Equal);
    }

    #[test]
    fn test_idiomatic_sublist() {
        assert_eq!(classify_idiomatic(&[1, 2, 3], &[0, 1, 2, 3, 4]), Sublist);
    }

    #[test]
    fn test_idiomatic_superlist() {
        assert_eq!(classify_idiomatic(&[0, 1, 2, 3, 4], &[1, 2, 3]), Superlist);
    }

    #[test]
    fn test_idiomatic_unequal() {
        assert_eq!(classify_idiomatic(&[1, 2, 3], &[4, 5, 6]), Unequal);
    }

    #[test]
    fn test_idiomatic_empty_sub_is_sublist() {
        assert_eq!(classify_idiomatic::<i32>(&[], &[1, 2, 3]), Sublist);
    }

    #[test]
    fn test_idiomatic_both_empty_equal() {
        assert_eq!(classify_idiomatic::<i32>(&[], &[]), Equal);
    }

    #[test]
    fn test_idiomatic_non_contiguous_not_sublist() {
        // [1,3] is NOT a contiguous sublist of [1,2,3]
        assert_eq!(classify_idiomatic(&[1, 3], &[1, 2, 3]), Unequal);
    }

    // --- recursive ---

    #[test]
    fn test_recursive_equal() {
        assert_eq!(classify_recursive(&[1, 2, 3], &[1, 2, 3]), Equal);
    }

    #[test]
    fn test_recursive_sublist() {
        assert_eq!(classify_recursive(&[1, 2, 3], &[0, 1, 2, 3, 4]), Sublist);
    }

    #[test]
    fn test_recursive_superlist() {
        assert_eq!(classify_recursive(&[0, 1, 2, 3, 4], &[1, 2, 3]), Superlist);
    }

    #[test]
    fn test_recursive_unequal() {
        assert_eq!(classify_recursive(&[1, 2, 3], &[4, 5, 6]), Unequal);
    }

    #[test]
    fn test_recursive_empty_sub_is_sublist() {
        assert_eq!(classify_recursive::<i32>(&[], &[1, 2, 3]), Sublist);
    }

    #[test]
    fn test_recursive_both_empty_equal() {
        assert_eq!(classify_recursive::<i32>(&[], &[]), Equal);
    }

    #[test]
    fn test_recursive_non_contiguous_not_sublist() {
        assert_eq!(classify_recursive(&[1, 3], &[1, 2, 3]), Unequal);
    }
}

Deep Comparison

OCaml vs Rust: Sublist Classification

Side-by-Side Code

OCaml

type relation = Equal | Sublist | Superlist | Unequal

let rec starts_with lst prefix = match lst, prefix with
  | _, [] -> true
  | [], _ -> false
  | h1 :: t1, h2 :: t2 -> h1 = h2 && starts_with t1 t2

let rec is_sublist sub lst = match lst with
  | [] -> sub = []
  | _ :: t -> starts_with lst sub || is_sublist sub t

let classify a b =
  if a = b then Equal
  else if is_sublist a b then Sublist
  else if is_sublist b a then Superlist
  else Unequal

Rust (idiomatic)

pub fn classify_idiomatic<T: PartialEq>(a: &[T], b: &[T]) -> Relation {
    if a == b {
        Relation::Equal
    } else if is_sublist_idiomatic(a, b) {
        Relation::Sublist
    } else if is_sublist_idiomatic(b, a) {
        Relation::Superlist
    } else {
        Relation::Unequal
    }
}

fn is_sublist_idiomatic<T: PartialEq>(sub: &[T], lst: &[T]) -> bool {
    if sub.is_empty() { return true; }
    lst.windows(sub.len()).any(|w| w == sub)
}

Rust (functional/recursive)

fn starts_with<T: PartialEq>(lst: &[T], prefix: &[T]) -> bool {
    match (lst, prefix) {
        (_, [])                      => true,
        ([], _)                      => false,
        ([h1, t1 @ ..], [h2, t2 @ ..]) => h1 == h2 && starts_with(t1, t2),
    }
}

fn is_sublist_recursive<T: PartialEq>(sub: &[T], lst: &[T]) -> bool {
    match lst {
        []             => sub.is_empty(),
        [_, rest @ ..] => starts_with(lst, sub) || is_sublist_recursive(sub, rest),
    }
}

Type Signatures

Concept	OCaml	Rust
Relation type	`type relation = Equal \\| Sublist \\| Superlist \\| Unequal`	`enum Relation { Equal, Sublist, Superlist, Unequal }`
Classify signature	`val classify : 'a list -> 'a list -> relation`	`fn classify<T: PartialEq>(a: &[T], b: &[T]) -> Relation`
List/slice type	`'a list`	`&[T]` (borrowed slice)
Equality constraint	implicit (structural `=`)	explicit `T: PartialEq` bound

Key Insights

**slice::windows** replaces the recursive prefix-checking loop entirely — it generates all overlapping sub-slices of a given length, enabling a clean .any() check.

Slice patterns ([h, rest @ ..]) in Rust match OCaml's h :: t perfectly, so the recursive solution is nearly a line-for-line translation.

Generic bounds: OCaml's structural equality is built-in; Rust requires an explicit T: PartialEq trait bound so the compiler knows == is valid for the element type.

Borrowing: both functions take &[T] (borrowed slices), avoiding unnecessary allocation — Rust guarantees no copies are made of the list data.

Performance: the idiomatic .windows() approach is O(n·m) but expressed in a single iterator chain with no heap allocation, while the recursive version has the same complexity with stack frames.

When to Use Each Style

Use idiomatic Rust when: you want concise, expressive code that leverages std slice methods — windows communicates the contiguous-subsequence intent directly. Use recursive Rust when: you are translating OCaml algorithms for educational purposes or when the recursive structure reflects the problem's natural induction principle more clearly.

Exercises

Extend the sublist classifier to return the starting index at which the first list appears within the second (for the Sublist case), returning None if not present.

Implement a longest_common_subsequence function that returns the LCS of two lists, and use it to check that the LCS of a sublist with its superlist equals the sublist.

Define a lattice of sublist relations (Equal < Sublist < Superlist < Unordered) and implement a most_specific function that classifies the relationship between a query list and a collection of lists.

Open Source Repos

functional-rust

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

Rust