002 Fundamental

Last Two Elements

ListsPattern Matching

Tutorial Video

Text description (accessibility)

This video demonstrates the "Last Two Elements" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Lists, Pattern Matching. Find the last two elements of a list. Key difference from OCaml: 1. **Return type:** OCaml returns `Some (x, y)` (owned copy); Rust returns `Option<(&T, &T)>` (borrowed references)

Tutorial

The Problem

Find the last two elements of a list. Return them as a pair (tuple), or None if the list has fewer than two elements.

The problem of finding trailing elements arises in streaming systems (keep the last k log entries), undo systems (last two states for delta computation), and sliding-window algorithms. The key insight is that slices in Rust provide O(1) random access, so taking the last two requires no traversal — unlike linked lists in OCaml where you must walk to the end.

🎯 Learning Outcomes

• Pattern matching on lists/slices with multiple cases

• Returning tuples (pairs) from functions

• Understanding Option<(T, T)> vs OCaml's option of (a * a)

• Using windows() for sliding-window iteration

• Recursive slice destructuring with [_, rest @ ..]

🦀 The Rust Way

Three approaches: (1) direct length-based indexing for O(1) access, (2) recursive slice patterns mirroring OCaml, and (3) windows(2).last() for an iterator-based solution. All return references (&T) to avoid cloning.

Code Example

pub fn last_two<T>(slice: &[T]) -> Option<(&T, &T)> {
    let len = slice.len();
    if len < 2 { None }
    else { Some((&slice[len - 2], &slice[len - 1])) }
}

let rec last_two = function
  | [] | [_] -> None
  | [x; y] -> Some (x, y)
  | _ :: t -> last_two t

Key Differences

Return type: OCaml returns Some (x, y) (owned copy); Rust returns Option<(&T, &T)> (borrowed references)

Tuple syntax: OCaml (x, y) vs Rust (x, y) — similar, but Rust tuples can hold references

Slice access: Rust slices are contiguous memory → O(1) indexing; OCaml lists are linked → O(n) traversal

Windows iterator: Rust's windows(n) has no direct OCaml equivalent — it exploits contiguous memory

Exhaustive matching: Both languages require exhaustive patterns, but Rust's slice patterns ([_, rest @ ..]) are less common than OCaml's list patterns

Efficiency: Rust's slice.len() + direct indexing is O(1); OCaml's recursive version is O(n) because linked lists don't store their length or tail pointer.

OCaml Approach

OCaml uses nested pattern matching: [] | [_] -> None, [x; y] -> Some (x, y), and _ :: t -> last_two t. The recursive structure naturally peels off the head until two elements remain.

The recursive OCaml version let rec last_two = function [] | [_] -> None | [x; y] -> Some (x, y) | _ :: t -> last_two t is idiomatic and clear, but O(n) because it must traverse the entire linked list. OCaml's List module does not cache the length or provide direct indexing, so walking to the end is unavoidable.

Full Source

#![allow(clippy::all)]
// Find the last two elements of a list, returning them as a tuple.

// ---------------------------------------------------------------------------
// Approach 1: Idiomatic Rust — slice pattern matching
// ---------------------------------------------------------------------------
// Slices in Rust support pattern matching similar to OCaml's list patterns.
// We borrow the slice (`&[T]`) to avoid taking ownership.
pub fn last_two<T>(slice: &[T]) -> Option<(&T, &T)> {
    let len = slice.len();
    if len < 2 {
        None
    } else {
        // Direct indexing — O(1) since slices are contiguous memory
        Some((&slice[len - 2], &slice[len - 1]))
    }
}

// ---------------------------------------------------------------------------
// Approach 2: Functional — recursive, mirrors the OCaml version
// ---------------------------------------------------------------------------
// Uses slice patterns `[x, y]` and `[_, rest @ ..]` for destructuring.
// Note: Rust doesn't guarantee TCO, but this is educational.
pub fn last_two_recursive<T>(slice: &[T]) -> Option<(&T, &T)> {
    match slice {
        // Empty or single element — no pair exists
        [] | [_] => None,
        // Exactly two elements — base case
        [x, y] => Some((x, y)),
        // More than two — recurse on tail (skip first element)
        [_, rest @ ..] => last_two_recursive(rest),
    }
}

// ---------------------------------------------------------------------------
// Approach 3: Iterator-based — using windows
// ---------------------------------------------------------------------------
// `windows(2)` gives sliding pairs; we take the last one.
pub fn last_two_windows<T>(slice: &[T]) -> Option<(&T, &T)> {
    // windows(2) yields &[T] slices of length 2
    slice.windows(2).last().map(|w| (&w[0], &w[1]))
}

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

    #[test]
    fn test_empty() {
        assert_eq!(last_two::<i32>(&[]), None);
        assert_eq!(last_two_recursive::<i32>(&[]), None);
        assert_eq!(last_two_windows::<i32>(&[]), None);
    }

    #[test]
    fn test_single() {
        assert_eq!(last_two(&[1]), None);
        assert_eq!(last_two_recursive(&[1]), None);
        assert_eq!(last_two_windows(&[1]), None);
    }

    #[test]
    fn test_two_elements() {
        assert_eq!(last_two(&[1, 2]), Some((&1, &2)));
        assert_eq!(last_two_recursive(&[1, 2]), Some((&1, &2)));
        assert_eq!(last_two_windows(&[1, 2]), Some((&1, &2)));
    }

    #[test]
    fn test_multiple() {
        assert_eq!(last_two(&[1, 2, 3, 4]), Some((&3, &4)));
        assert_eq!(last_two_recursive(&[1, 2, 3, 4]), Some((&3, &4)));
        assert_eq!(last_two_windows(&[1, 2, 3, 4]), Some((&3, &4)));
    }

    #[test]
    fn test_strings() {
        let v = ["a", "b", "c", "d"];
        assert_eq!(last_two(&v), Some((&"c", &"d")));
    }
}

(* Find the last two elements of a list *)

let rec last_two = function
  | [] | [_] -> None
  | [x; y] -> Some (x, y)
  | _ :: t -> last_two t

(* Tests *)
let () =
  assert (last_two [] = None);
  assert (last_two [1] = None);
  assert (last_two [1; 2] = Some (1, 2));
  assert (last_two [1; 2; 3; 4] = Some (3, 4));
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_empty() {
        assert_eq!(last_two::<i32>(&[]), None);
        assert_eq!(last_two_recursive::<i32>(&[]), None);
        assert_eq!(last_two_windows::<i32>(&[]), None);
    }

    #[test]
    fn test_single() {
        assert_eq!(last_two(&[1]), None);
        assert_eq!(last_two_recursive(&[1]), None);
        assert_eq!(last_two_windows(&[1]), None);
    }

    #[test]
    fn test_two_elements() {
        assert_eq!(last_two(&[1, 2]), Some((&1, &2)));
        assert_eq!(last_two_recursive(&[1, 2]), Some((&1, &2)));
        assert_eq!(last_two_windows(&[1, 2]), Some((&1, &2)));
    }

    #[test]
    fn test_multiple() {
        assert_eq!(last_two(&[1, 2, 3, 4]), Some((&3, &4)));
        assert_eq!(last_two_recursive(&[1, 2, 3, 4]), Some((&3, &4)));
        assert_eq!(last_two_windows(&[1, 2, 3, 4]), Some((&3, &4)));
    }

    #[test]
    fn test_strings() {
        let v = ["a", "b", "c", "d"];
        assert_eq!(last_two(&v), Some((&"c", &"d")));
    }
}

Deep Comparison

Comparison: Last Two Elements

OCaml

let rec last_two = function
  | [] | [_] -> None
  | [x; y] -> Some (x, y)
  | _ :: t -> last_two t

Rust — Idiomatic (direct indexing)

pub fn last_two<T>(slice: &[T]) -> Option<(&T, &T)> {
    let len = slice.len();
    if len < 2 { None }
    else { Some((&slice[len - 2], &slice[len - 1])) }
}

Rust — Functional (recursive)

pub fn last_two_recursive<T>(slice: &[T]) -> Option<(&T, &T)> {
    match slice {
        [] | [_] => None,
        [x, y] => Some((x, y)),
        [_, rest @ ..] => last_two_recursive(rest),
    }
}

Rust — Iterator (windows)

pub fn last_two_windows<T>(slice: &[T]) -> Option<(&T, &T)> {
    slice.windows(2).last().map(|w| (&w[0], &w[1]))
}

Comparison Table

Aspect	OCaml	Rust
Data structure	`'a list` (linked list)	`&[T]` (slice / contiguous)
Return type	`('a * 'a) option`	`Option<(&T, &T)>`
Ownership	Copies values into tuple	Borrows references
Pattern syntax	`[x; y]`	`[x, y]`
Complexity	O(n) always	O(1) idiomatic, O(n) recursive

Type Signatures

• OCaml: val last_two : 'a list -> ('a * 'a) option

• Rust: fn last_two<T>(slice: &[T]) -> Option<(&T, &T)>

Takeaways

Rust's contiguous memory layout enables O(1) access to the last two elements — OCaml's linked list requires full traversal

Rust returns borrowed references (&T) instead of copies, avoiding allocation for large types

Slice pattern matching in Rust ([x, y], [_, rest @ ..]) closely mirrors OCaml's list patterns

The windows() iterator is uniquely Rust — it exploits contiguous memory for sliding-window views

Both languages use Option/option to safely handle the "not enough elements" case without exceptions

Exercises

Write last_n that returns the last n elements of a slice as an Option<&[T]>, returning None if the slice is shorter than n.

Implement last_two_by that returns the last two elements of a slice satisfying a predicate, using only iterator combinators.

Write a generic sliding_last that yields all consecutive windows of size k from the end of a list, collecting them into a Vec<Vec<T>>.

Generic version: Rewrite last_two to be generic over T: Clone, returning Option<(T, T)> (owned values instead of references). When is this better than returning references?

Performance comparison: Write a benchmark comparing last_two (direct indexing), last_two_recursive, and last_two_windows for slices of 10, 1000, and 1,000,000 elements.

Open Source Repos

functional-rust

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

Rust