019 — Rotate a List to the Left
Tutorial Video
Text description (accessibility)
This video demonstrates the "019 — Rotate a List to the Left" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Rotating a list left by n positions — moving the first n elements to the end — is a fundamental circular buffer operation. Key difference from OCaml: 1. **In
Tutorial
The Problem
Rotating a list left by n positions — moving the first n elements to the end — is a fundamental circular buffer operation. It appears in round-robin schedulers (rotating the job queue), circular queues, cryptographic operations (bit rotation in SHA, AES), polynomial arithmetic (cyclic shift), and visual animation (scrolling backgrounds).
The efficient algorithm avoids creating intermediate lists: for a list of length len, rotating by n % len combines two split-and-concatenate operations. This is equivalent to the "juggling algorithm" and the "reversal algorithm" for in-place rotation.
🎯 Learning Outcomes
rotate(v, n) = v[n..] ++ v[..n]n % len[n..].to_vec() extended with [..n] for clear, correct rotationn % v.len() to normalize rotations larger than the list length before slicingv.rotate_left(n) for O(n) in-place rotation with no allocationCode Example
#![allow(clippy::all)]
// Placeholder — pending conversionKey Differences
v.rotate_left(n) mutates Vec in place using a three-reversal algorithm — O(n) time, O(1) space. OCaml's immutable lists always allocate new structure.rotate_left panics on n > len; normalize first. OCaml needs ((n mod len) + len) mod len to handle negative values.@ vs extend_from_slice**: OCaml's right @ left is O(|right|) because it copies the right list. Rust's extend_from_slice appends in O(n) but avoids an intermediate allocation if capacity allows.split_at performance**: Rust's split is O(1) (pointer arithmetic). OCaml's List.length + split are O(n) each.rotate_left built-in:** Rust's slice::rotate_left(n) is a built-in method that rotates in place using three reversals — O(n), no allocation. OCaml has no built-in rotation.[n..] ++ [..n]:** The immutable Rust version uses [&v[n..], &v[..n]].concat() — O(n) with one allocation. OCaml uses right @ left — O(|right|) with one allocation.n % v.len() handles rotations larger than the list length. Always normalize before accessing slice indices to avoid panics.OCaml Approach
OCaml's version: let rotate lst n = let len = List.length lst in let n = ((n mod len) + len) mod len in let (left, right) = split lst n in right @ left. The ((n mod len) + len) mod len handles negative rotations correctly. split from example 017 decomposes the list, and @ concatenates. OCaml's @ is O(|left|), making this O(n) overall.
OCaml's rotate uses split_at then appends: let rotate list n = let len = List.length list in let n' = n mod len in let (left, right) = split_at n' list in right @ left. The @ operator copies the left half — O(|right|). Negative rotation is achieved by normalizing: ((n mod len) + len) mod len.
Full Source
#![allow(clippy::all)]
// Placeholder — pending conversionDeep Comparison
OCaml vs Rust: Rotate Left
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
rotate_right(v: &[i32], n: usize) -> Vec<i32> using rotate_left with appropriate adjustment.caesar_encrypt(text: &str, shift: usize) -> String using rotate_left on the alphabet.is_rotation(a: &[i32], b: &[i32]) -> bool that returns true if b is a rotation of a. Use the classic trick of checking if b is a subarray of a ++ a.rotate_right(v: &[T], n: usize) -> Vec<T> — rotating right by n is the same as rotating left by v.len() - n. Use v.rotate_left for the in-place version.cyclic_iter(v: &[T], start: usize) -> impl Iterator<Item = &T> that starts at index start and cycles through the slice indefinitely — equivalent to an infinite rotating view.