018 — Extract a Slice from a List
Tutorial Video
Text description (accessibility)
This video demonstrates the "018 — Extract a Slice from a List" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Extracting a contiguous subsequence from positions i to k (OCaml 99 Problems #18) is the subarray operation. Key difference from OCaml: 1. **O(1) vs O(n)**: Rust's `&v[i..k]` is a zero
Tutorial
The Problem
Extracting a contiguous subsequence from positions i to k (OCaml 99 Problems #18) is the subarray operation. It is one of the most common list operations: substring extraction in text editors, windowed queries in time-series databases, submatrix extraction in linear algebra, and range queries in sorted data structures all reduce to slice extraction.
The key insight is understanding indexing conventions: OCaml 99 Problems uses 1-based inclusive indexing [i..k], while Rust slices use 0-based exclusive end [i..k]. Getting the off-by-one right is a classic source of bugs, and this problem forces careful reasoning about boundary conditions.
🎯 Learning Outcomes
&v[start..end] for O(1) subarray extractionv.get(start..end) returning Option<&[T]> for safe slicing that avoids panics on invalid indicesCode Example
#![allow(clippy::all)]
// Placeholder — pending conversionKey Differences
&v[i..k] is a zero-copy O(1) borrow of existing memory. OCaml's recursive extraction is O(k-i) because it traverses from the start of the list.[i, k]. Rust slices use 0-based exclusive end [i, k) or inclusive [i..=k]. Always clarify the convention..get(i..k) returning Option<&[T]> for safe access. OCaml's version silently stops at end of list.&v[i..k] borrows without copying. v[i..k].to_vec() copies. OCaml always allocates a new list.&v[i..k] returns a reference into existing memory — no allocation. OCaml must build a new list by traversal — O(k-i).[i..k] or inclusive end for [i..=k]. Document clearly which convention your function uses.get(i..k) which returns Option<&[T]> for safe slicing.OCaml Approach
OCaml's version uses 1-based indexing: let slice lst i k = let rec aux acc n = function | [] -> List.rev acc | x :: t -> if n > k then List.rev acc else if n < i then aux acc (n+1) t else aux (x :: acc) (n+1) t in aux [] 1 lst. The counter n advances through 1-based positions, collecting elements from i to k inclusive.
OCaml's sub list i k (1-based inclusive) uses a recursive countdown: skip the first i-1 elements, then take the next k-i+1 elements. There is no direct equivalent to Rust's &v[i..=k]. OCaml's List module doesn't provide a slice operation — only third-party libraries like Core.List.sub offer it.
Full Source
#![allow(clippy::all)]
// Placeholder — pending conversionDeep Comparison
OCaml vs Rust: Slice List
Overview
See the example.rs and example.ml files for detailed implementations.
Key Differences
| Aspect | OCaml | Rust |
|---|---|---|
| Type system | Hindley-Milner | Ownership + traits |
| Memory | GC | Zero-cost abstractions |
| Mutability | Explicit ref | mut keyword |
| Error handling | Option/Result | Result<T, E> |
See README.md for detailed comparison.
Exercises
windows_of(v: &[i32], size: usize) -> Vec<&[i32]> that returns all contiguous subsequences of length size. Use Rust's built-in v.windows(size).circular_slice(v: &[i32], start: usize, len: usize) -> Vec<i32> that wraps around the end of the vector using modular arithmetic.select(v: &[i32], indices: &[usize]) -> Vec<i32> that extracts elements at the specified positions (generalization of slice).windows(list: &[T], width: usize) -> Vec<&[T]> returning all contiguous windows of the given width. Compare with Rust's built-in .windows(width) method.safe_slice(v: &[T], start: usize, end: usize) -> Option<&[T]> that returns None instead of panicking when indices are out of bounds. Use v.get(start..end).