List Map From Scratch
ListsHigher-Order Functions
Tutorial Video
Text description (accessibility)
This video demonstrates the "List Map From Scratch" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Lists, Higher-Order Functions. Implement the `map` function—a higher-order function that applies a transformation function to each element of a list. Key difference from OCaml: 1. **List vs Slice representation:** OCaml uses a linked list `'a list`; Rust uses slices `&[T]` for borrowed views of contiguous data. Slices are cheaper to work with but require `Copy` bounds for element operations.
Tutorial
The Problem
Implement the map function—a higher-order function that applies a transformation function to each element of a list. Demonstrate how abstracting this common pattern (apply f to each element) enables partial application: binding map with specific functions creates specialized transformers.
Building map from scratch is the canonical first exercise in functional programming because it forces you to understand the abstraction you are hiding. Every senior developer should know that for (item of items) result.push(f(item)) is just items.map(f). Making this abstraction a first-class value — a function that takes other functions — is what enables predicate factories, transformer pipelines, and the entire functional style.
🎯 Learning Outcomes
Fn) parallel OCaml's function typesCopy is required when working with borrowed slices, and when to use &[T] vs Vec<T>🦀 The Rust Way
Idiomatic Rust leverages iterators: .iter().map(f).collect() is the standard, efficient way to apply a transformation. For teaching the abstraction principle, we also show the explicit recursive version. Rust closures capture their environment, making partial application natural: |x| x + 1 is a closure, and binding map(|x| x + 1, items) creates the transformation inline.
Code Example
// Idiomatic Rust: use iterator chains with the built-in map
pub fn map_idiomatic<T, U, F>(f: F, items: &[T]) -> Vec<U>
where
F: Fn(T) -> U,
T: Copy,
{
items.iter().map(|&x| f(x)).collect()
}
// Partial application in Rust: wrap map with a closure that captures the function
pub fn add_one(items: &[i32]) -> Vec<i32> {
map(|x| x + 1, items)
}
pub fn to_string_int(items: &[i32]) -> Vec<String> {
map(|x| x.to_string(), items)
}
pub fn double(items: &[i32]) -> Vec<i32> {
map(|x| x * 2, items)
}
// Usage
fn main() {
let nums = &[1, 2, 3, 4, 5];
println!("{:?}", add_one(nums)); // [2, 3, 4, 5, 6]
println!("{:?}", to_string_int(nums)); // ["1", "2", "3", "4", "5"]
println!("{:?}", double(nums)); // [2, 4, 6, 8, 10]
}Key Differences
'a list; Rust uses slices &[T] for borrowed views of contiguous data. Slices are cheaper to work with but require Copy bounds for element operations.[head, rest @ ..] to deconstruct and recurse.let add1 = map (fun x -> x + 1) automatically returns a function. Rust requires explicit closure syntax: |x| x + 1, and capturing the function in a closure returned by a wrapper function.List.map; Rust learners typically use the iterator map method. The explicit implementation teaches the abstraction, but production code uses iterators.map with other list functions via piping; Rust chains methods or uses closure composition, reflecting different language paradigms.'a list; Rust uses slices &[T] for borrowed views of contiguous data. Slices are cheaper to work with but require Copy bounds for element operations.map f partially applies to create a transformer. Rust needs an explicit closure: |items| map_idiomatic(f, items).Vec per recursive frame. The iterator version collects once at the end.T: Copy when extracting values from a borrowed slice by value. OCaml's GC handles ownership transparently — no bounds needed.'a -> 'b. Rust: impl Fn(T) -> U for closures or fn(T) -> U for function pointers.OCaml Approach
OCaml's map is recursive and explicit: match on the list structure (empty or head::tail), apply the function to the head, and recursively process the tail. OCaml's automatic currying makes partial application effortless—let add1 = map (fun x -> x + 1) creates a specialized transformer function without extra syntax.
Full Source
#![allow(clippy::all)]
// Idiomatic Rust: use the iterator-based map directly from std
// This is how Rust developers write it — leveraging the standard library
pub fn map_idiomatic<T, U, F>(f: F, items: &[T]) -> Vec<U>
where
F: Fn(T) -> U,
T: Copy,
{
items.iter().map(|&x| f(x)).collect()
}
// Functional/recursive: explicit recursion similar to OCaml
// Shows the abstraction principle: we extract the common pattern (apply f to each element)
pub fn map_recursive<T, U, F>(f: F, items: &[T]) -> Vec<U>
where
F: Fn(T) -> U,
T: Copy,
{
match items {
[] => Vec::new(),
[head, rest @ ..] => {
let mut result = vec![f(*head)];
result.extend(map_recursive(f, rest));
result
}
}
}
// Generic map over slices — the fundamental abstraction
// This demonstrates partial application: we can bind this to create specialized functions
pub fn map<T, U, F>(f: F, items: &[T]) -> Vec<U>
where
F: Fn(T) -> U,
T: Copy,
{
map_idiomatic(f, items)
}
// Partial application examples — creating specialized transformers by binding map with specific functions
pub fn add_one(items: &[i32]) -> Vec<i32> {
map(|x| x + 1, items)
}
pub fn to_string_int(items: &[i32]) -> Vec<String> {
map(|x| x.to_string(), items)
}
pub fn double(items: &[i32]) -> Vec<i32> {
map(|x| x * 2, items)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_map_empty() {
let empty: &[i32] = &[];
let result = map(|x| x + 1, empty);
assert_eq!(result, vec![]);
}
#[test]
fn test_map_single() {
let result = map(|x| x + 1, &[5]);
assert_eq!(result, vec![6]);
}
#[test]
fn test_map_multiple() {
let result = map(|x| x + 1, &[1, 2, 3, 4, 5]);
assert_eq!(result, vec![2, 3, 4, 5, 6]);
}
#[test]
fn test_add_one() {
let nums = vec![1, 2, 3, 4, 5];
let result = add_one(&nums);
assert_eq!(result, vec![2, 3, 4, 5, 6]);
}
#[test]
fn test_to_string_int() {
let nums = vec![1, 2, 3];
let result = to_string_int(&nums);
assert_eq!(result, vec!["1", "2", "3"]);
}
#[test]
fn test_double() {
let nums = vec![1, 2, 3, 4, 5];
let result = double(&nums);
assert_eq!(result, vec![2, 4, 6, 8, 10]);
}
#[test]
fn test_map_recursive() {
let result = map_recursive(|x| x * 2, &[1, 2, 3]);
assert_eq!(result, vec![2, 4, 6]);
}
#[test]
fn test_recursive_vs_idiomatic() {
let nums = &[1, 2, 3, 4, 5];
let idiomatic = map_idiomatic(|x| x + 1, nums);
let recursive = map_recursive(|x| x + 1, nums);
assert_eq!(idiomatic, recursive);
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_map_empty() {
let empty: &[i32] = &[];
let result = map(|x| x + 1, empty);
assert_eq!(result, vec![]);
}
#[test]
fn test_map_single() {
let result = map(|x| x + 1, &[5]);
assert_eq!(result, vec![6]);
}
#[test]
fn test_map_multiple() {
let result = map(|x| x + 1, &[1, 2, 3, 4, 5]);
assert_eq!(result, vec![2, 3, 4, 5, 6]);
}
#[test]
fn test_add_one() {
let nums = vec![1, 2, 3, 4, 5];
let result = add_one(&nums);
assert_eq!(result, vec![2, 3, 4, 5, 6]);
}
#[test]
fn test_to_string_int() {
let nums = vec![1, 2, 3];
let result = to_string_int(&nums);
assert_eq!(result, vec!["1", "2", "3"]);
}
#[test]
fn test_double() {
let nums = vec![1, 2, 3, 4, 5];
let result = double(&nums);
assert_eq!(result, vec![2, 4, 6, 8, 10]);
}
#[test]
fn test_map_recursive() {
let result = map_recursive(|x| x * 2, &[1, 2, 3]);
assert_eq!(result, vec![2, 4, 6]);
}
#[test]
fn test_recursive_vs_idiomatic() {
let nums = &[1, 2, 3, 4, 5];
let idiomatic = map_idiomatic(|x| x + 1, nums);
let recursive = map_recursive(|x| x + 1, nums);
assert_eq!(idiomatic, recursive);
}
}Deep Comparison
OCaml vs Rust: List Map From Scratch
Side-by-Side Code
OCaml
(* Recursive abstraction: extract the pattern of applying f to each element *)
let rec map f = function
| [] -> []
| h :: t ->
let h' = f h in
h' :: map f t
(* Partial application: bind map to a specific function *)
let add1 = map (fun x -> x + 1)
let to_string = map string_of_int
let double = map (fun x -> x * 2)
(* Usage: apply the specialized transformers *)
let nums = [1; 2; 3; 4; 5]
let () =
List.iter (Printf.printf "%d ") (add1 nums); (* [2; 3; 4; 5; 6] *)
List.iter (Printf.printf "%s ") (to_string nums); (* ["1"; "2"; "3"; "4"; "5"] *)
List.iter (Printf.printf "%d ") (double nums) (* [2; 4; 6; 8; 10] *)
Rust (idiomatic)
// Idiomatic Rust: use iterator chains with the built-in map
pub fn map_idiomatic<T, U, F>(f: F, items: &[T]) -> Vec<U>
where
F: Fn(T) -> U,
T: Copy,
{
items.iter().map(|&x| f(x)).collect()
}
// Partial application in Rust: wrap map with a closure that captures the function
pub fn add_one(items: &[i32]) -> Vec<i32> {
map(|x| x + 1, items)
}
pub fn to_string_int(items: &[i32]) -> Vec<String> {
map(|x| x.to_string(), items)
}
pub fn double(items: &[i32]) -> Vec<i32> {
map(|x| x * 2, items)
}
// Usage
fn main() {
let nums = &[1, 2, 3, 4, 5];
println!("{:?}", add_one(nums)); // [2, 3, 4, 5, 6]
println!("{:?}", to_string_int(nums)); // ["1", "2", "3", "4", "5"]
println!("{:?}", double(nums)); // [2, 4, 6, 8, 10]
}
Rust (functional/recursive)
// Recursive Rust: explicit recursion with slice pattern matching
pub fn map_recursive<T, U, F>(f: F, items: &[T]) -> Vec<U>
where
F: Fn(T) -> U,
T: Copy,
{
match items {
[] => Vec::new(),
[head, rest @ ..] => {
let mut result = vec![f(*head)];
result.extend(map_recursive(f, rest));
result
}
}
}
// Demonstrates the same abstraction: extract and compose the per-element operation
// with the recursive structure of the list
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| Function type signature | ('a -> 'b) -> 'a list -> 'b list | fn map<T, U, F>(f: F, items: &[T]) -> Vec<U> where F: Fn(T) -> U, T: Copy |
| Partial application (add1) | int list -> int list | fn add_one(items: &[i32]) -> Vec<i32> |
| List representation | 'a list (linked list) | &[T] (slice) or Vec<T> (heap-allocated) |
| Function parameter | 'a -> 'b (implicit currying) | F where F: Fn(T) -> U (trait bound) |
| Optional value | N/A (returns list) | Vec<U> (always returns a vector) |
Key Insights
Copy bounds when elements are borrowed. The Vec return type allocates on the heap, mirroring OCaml's list construction..iter().map().collect()) are preferred for clarity and safety. Both express the same transformation; iterators avoid stack overhead for large lists.Fn trait bounds replace OCaml's implicit function types. The bound F: Fn(T) -> U means "F is a callable that takes T and returns U"—equivalent to OCaml's 'a -> 'b, but explicit in the code.map requires T: Copy to borrow elements efficiently. This constraint is absent in OCaml because all values are boxed. The Copy bound ensures we don't move data from the borrowed slice; without it, we'd need to clone or take ownership, changing the semantics.When to Use Each Style
Use idiomatic Rust when: Writing production code that transforms lists, ranges, or iterables. Iterator chains are readable, efficient, and compose naturally: nums.iter().map(f).filter(g).collect().
Use recursive Rust when: Teaching functional abstraction, demonstrating the structural recursion pattern, or implementing custom list types where recursion is the only option. Recursive implementations are slower (stack overhead) but reveal the underlying algorithm.
Use OCaml when: Exploring rapid prototyping of algorithms, mathematical transformations, or functional patterns where currying and pattern matching shine. OCaml's implicit partial application makes higher-order functions feel lightweight.
Exercises
map_index — a variant of map that passes both the element and its index to the mapping function.flat_map from scratch: given a list and a function f: T -> Vec<U>, return a flattened Vec<U> without using .flat_map().map_result that applies a fallible function f: T -> Result<U, E> to each element, returning Ok(Vec<U>) if all succeed or the first Err.