003 Fundamental

K-th Element

ListsIndexing

Tutorial Video

Text description (accessibility)

This video demonstrates the "K-th Element" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Lists, Indexing. Find the k-th element of a list. Key difference from OCaml: 1. **Indexing convention:** OCaml uses 1

Tutorial

The Problem

Find the k-th element of a list. The OCaml version uses 1-based indexing. We provide both 1-based (matching OCaml) and 0-based (idiomatic Rust) versions.

Safe element access by index is a universal problem. Languages like C use raw pointer arithmetic and segfault on out-of-bounds access. Java throws IndexOutOfBoundsException at runtime. Rust's get(index) returns Option<&T>, making the possibility of out-of-bounds explicit at the type level, forcing callers to handle both cases before using the value. This is one of the simplest but most impactful applications of the Option type.

🎯 Learning Outcomes

• Safe indexing with Option return types (no panics)

• Understanding 0-based vs 1-based indexing conventions

• slice.get(i) as the idiomatic safe accessor in Rust

• Recursive indexing via slice pattern matching

• How Rust's ExactSizeIterator makes .nth() O(1) on slices

🦀 The Rust Way

slice.get(index) provides O(1) safe access. The recursive version uses slice patterns to mirror OCaml. A 1-based wrapper handles the indexing convention difference.

Code Example

pub fn at<T>(slice: &[T], index: usize) -> Option<&T> {
    slice.get(index)
}

let rec at k = function
  | [] -> None
  | h :: t -> if k = 1 then Some h else at (k - 1) t

Key Differences

Indexing convention: OCaml uses 1-based; Rust uses 0-based (we provide both)

Access complexity: Rust slices → O(1) random access; OCaml lists → O(k) traversal

Safe access: Rust's .get() returns Option<&T>; OCaml's pattern match returns option

Borrowing: Rust returns &T (reference); OCaml copies the value

Underflow risk: 1-based k - 1 can underflow usize in Rust — must guard against k = 0

Complexity: slice.get(i) is O(1); OCaml's List.nth l n is O(n). This is the fundamental performance argument for arrays over linked lists in most practical use cases.

Indexing convention: OCaml 99 Problems uses 1-based indexing (element 1 is the first). Rust and most modern languages use 0-based indexing. Always document which convention your function uses.

OCaml Approach

Recursive pattern match: if k = 1, return the head; otherwise recurse on the tail with k - 1. Returns None for empty lists. Natural and concise with linked lists.

OCaml's List.nth list n raises Failure "nth" or Invalid_argument on invalid indices — runtime exceptions. A safe OCaml version: let rec nth_safe = function | ([], _) -> None | (x :: _, 1) -> Some x | (_ :: t, n) -> nth_safe (t, n-1). Note that accessing the nth element in a linked list is O(n) — this is an inherent limitation of the data structure, not an implementation choice.

Full Source

#![allow(clippy::all)]
// Find the k-th element of a list. The OCaml version uses 1-based indexing.
// We provide both 1-based (matching OCaml) and 0-based (idiomatic Rust) versions.

// ---------------------------------------------------------------------------
// Approach 1: Idiomatic Rust — direct indexing (0-based)
// ---------------------------------------------------------------------------
// Slices support `.get(index)` which returns `Option<&T>` — safe, no panic.
pub fn at<T>(slice: &[T], index: usize) -> Option<&T> {
    // .get() does bounds checking and returns None if out of range
    slice.get(index)
}

// ---------------------------------------------------------------------------
// Approach 2: 1-based indexing (matches OCaml semantics)
// ---------------------------------------------------------------------------
// OCaml's `at k list` uses 1-based indexing. We replicate that here.
pub fn at_one_based<T>(slice: &[T], k: usize) -> Option<&T> {
    if k == 0 {
        None // 1-based: 0 is invalid
    } else {
        slice.get(k - 1)
    }
}

// ---------------------------------------------------------------------------
// Approach 3: Functional — recursive, mirrors OCaml's pattern matching
// ---------------------------------------------------------------------------
// Uses 1-based indexing like the OCaml version.
// Recursion on slices: `[h, rest @ ..]` destructures head and tail.
pub fn at_recursive<T>(slice: &[T], k: usize) -> Option<&T> {
    match (slice, k) {
        ([], _) => None,
        ([h, ..], 1) => Some(h),
        ([_, rest @ ..], k) => at_recursive(rest, k - 1),
    }
}

// ---------------------------------------------------------------------------
// Approach 4: Iterator-based
// ---------------------------------------------------------------------------
pub fn at_iter<T>(slice: &[T], index: usize) -> Option<&T> {
    // .get() is idiomatic for slices; .iter().nth() would also work but clippy
    // prefers direct indexing on slices.
    slice.get(index)
}

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

    #[test]
    fn test_basic() {
        let v = [1, 2, 3, 4, 5];
        assert_eq!(at(&v, 2), Some(&3)); // 0-based: index 2 = third element
        assert_eq!(at_one_based(&v, 3), Some(&3)); // 1-based: k=3
        assert_eq!(at_recursive(&v, 3), Some(&3)); // 1-based
        assert_eq!(at_iter(&v, 2), Some(&3)); // 0-based
    }

    #[test]
    fn test_first() {
        let v = [1, 2, 3];
        assert_eq!(at(&v, 0), Some(&1));
        assert_eq!(at_one_based(&v, 1), Some(&1));
        assert_eq!(at_recursive(&v, 1), Some(&1));
    }

    #[test]
    fn test_out_of_bounds() {
        let v = [1, 2, 3];
        assert_eq!(at(&v, 10), None);
        assert_eq!(at_one_based(&v, 10), None);
        assert_eq!(at_recursive(&v, 10), None);
    }

    #[test]
    fn test_empty() {
        assert_eq!(at::<i32>(&[], 0), None);
        assert_eq!(at_one_based::<i32>(&[], 1), None);
        assert_eq!(at_recursive::<i32>(&[], 1), None);
    }

    #[test]
    fn test_one_based_zero() {
        let v = [1, 2, 3];
        assert_eq!(at_one_based(&v, 0), None); // 0 is invalid for 1-based
    }
}

(* Find the k-th element (1-indexed) *)

let rec at k = function
  | [] -> None
  | h :: t -> if k = 1 then Some h else at (k - 1) t

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

✓ Tests Rust test suite

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

    #[test]
    fn test_basic() {
        let v = [1, 2, 3, 4, 5];
        assert_eq!(at(&v, 2), Some(&3)); // 0-based: index 2 = third element
        assert_eq!(at_one_based(&v, 3), Some(&3)); // 1-based: k=3
        assert_eq!(at_recursive(&v, 3), Some(&3)); // 1-based
        assert_eq!(at_iter(&v, 2), Some(&3)); // 0-based
    }

    #[test]
    fn test_first() {
        let v = [1, 2, 3];
        assert_eq!(at(&v, 0), Some(&1));
        assert_eq!(at_one_based(&v, 1), Some(&1));
        assert_eq!(at_recursive(&v, 1), Some(&1));
    }

    #[test]
    fn test_out_of_bounds() {
        let v = [1, 2, 3];
        assert_eq!(at(&v, 10), None);
        assert_eq!(at_one_based(&v, 10), None);
        assert_eq!(at_recursive(&v, 10), None);
    }

    #[test]
    fn test_empty() {
        assert_eq!(at::<i32>(&[], 0), None);
        assert_eq!(at_one_based::<i32>(&[], 1), None);
        assert_eq!(at_recursive::<i32>(&[], 1), None);
    }

    #[test]
    fn test_one_based_zero() {
        let v = [1, 2, 3];
        assert_eq!(at_one_based(&v, 0), None); // 0 is invalid for 1-based
    }
}

Deep Comparison

Comparison: K-th Element

OCaml

let rec at k = function
  | [] -> None
  | h :: t -> if k = 1 then Some h else at (k - 1) t

Rust — Idiomatic (safe indexing)

pub fn at<T>(slice: &[T], index: usize) -> Option<&T> {
    slice.get(index)
}

Rust — 1-based (matching OCaml)

pub fn at_one_based<T>(slice: &[T], k: usize) -> Option<&T> {
    if k == 0 { None } else { slice.get(k - 1) }
}

Rust — Functional (recursive)

pub fn at_recursive<T>(slice: &[T], k: usize) -> Option<&T> {
    match (slice, k) {
        ([], _) => None,
        ([h, ..], 1) => Some(h),
        ([_, rest @ ..], k) => at_recursive(rest, k - 1),
    }
}

Comparison Table

Aspect	OCaml	Rust
Indexing	1-based	0-based (idiomatic)
Data structure	`'a list` (linked)	`&[T]` (contiguous)
Access time	O(k)	O(1)
Return	`'a option` (copy)	`Option<&T>` (borrow)
Bounds check	Pattern match	`.get()` returns `None`

Type Signatures

• OCaml: val at : int -> 'a list -> 'a option

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

Takeaways

Rust's .get() is a one-liner that replaces OCaml's entire recursive function — contiguous memory wins

The 0-based vs 1-based convention matters: usize subtraction can panic on underflow in Rust

OCaml's int allows negative indices (returns None); Rust's usize is unsigned — different safety properties

Recursive slice matching works but is purely educational — .get() is always preferred in production Rust

Both languages encode "might not exist" in the type system (Option/option) rather than throwing exceptions

Exercises

Write kth_from_end that returns the k-th element counting from the end of the list (1-indexed), returning None if out of bounds.

Implement every_kth that collects every k-th element of a slice into a new Vec (e.g., every 3rd element starting from index k-1).

Write kth_element_sorted that finds the k-th smallest element of an unsorted slice without fully sorting it (selection algorithm), returning None if k exceeds the length.

Safe index: Write a wrapper type SafeIndex<T> that wraps a &[T] and implements Index<usize> returning Option<&T> instead of panicking.

Negative indexing: Implement at_from_end(slice: &[T], k: usize) -> Option<&T> where k=1 is the last element, like Python's list[-1] — without using negative numbers.

Open Source Repos

functional-rust

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

Rust