054: List Map from Scratch

Difficulty: 1 Level: Beginner Implement `map` from first principles — and discover it's a special case of `fold`.

The Problem This Solves

You have a list of numbers and you want a list of their squares. A list of filenames and you want a list of file sizes. A list of users and you want a list of their emails. The operation is always the same: walk the list, apply a transformation to each element, collect the results. Without `map`, you write a `for` loop, a mutable accumulator, and the same boilerplate for every transformation. The loop structure obscures the intent. With `map`, you declare the transformation and `map` handles the iteration — the loop is gone, only the logic remains. The deeper lesson: `add1`, `to_string`, and `double` all have the same shape. The Abstraction Principle says when two functions share a shape, factor out the difference into a parameter. `map` is that factoring — it takes the transformation as a parameter.

The Intuition

`map` is a conveyor belt. Each item on the belt goes through a machine (your function `f`) and comes out the other side transformed. The belt is the same; only the machine changes. In OCaml, `map` recurses over a cons-list: empty list produces empty list, head gets transformed and prepended to the recursively mapped tail. In Rust, the iterator does the walking; you just describe the transformation.

How It Works in Rust

// Idiomatic: iterator adapter
pub fn map<A, B, F: Fn(&A) -> B>(list: &[A], f: F) -> Vec<B> {
 list.iter().map(f).collect()
}

// Recursive: mirrors OCaml's head-cons pattern
pub fn map_recursive<A, B, F: Fn(&A) -> B>(list: &[A], f: F) -> Vec<B> {
 match list {
     [] => vec![],
     [head, tail @ ..] => {  // [head, tail @ ..] ≈ OCaml's h :: t
         let mut result = vec![f(head)];
         result.extend(map_recursive(tail, f));
         result
     }
 }
}

// Fold: map as a fold over an accumulator
pub fn map_fold<A, B, F: Fn(&A) -> B>(list: &[A], f: F) -> Vec<B> {
 list.iter().fold(Vec::new(), |mut acc, x| {
     acc.push(f(x));  // fold accumulates transformed elements
     acc
 })
}

All three produce the same result. The fold version reveals that `map` is mechanically a `fold` — fold is the universal list combinator, and `map` is one of its specialisations.

What This Unlocks

Any element-wise transformation — change types, compute derived values, format for display.
Understanding fold's universality — `map` and `filter` are both derivable from `fold`; this example shows the first half.
Slice patterns — `[head, tail @ ..]` is the Rust idiom for recursive list processing, directly mirroring OCaml's `h :: t`.

Key Differences

Concept	OCaml	Rust
Type signature	`('a -> 'b) -> 'a list -> 'b list`	`fn<A, B, F: Fn(&A)->B>(list: &[A], f: F) -> Vec<B>`
Head-tail pattern	`h :: t`	`[head, tail @ ..]`
Partial application	`let add1 = map (fun x -> x+1)`	Explicit closure or wrapper function
Allocation	GC manages cons cells	`collect()` allocates one `Vec`
Iterator version	`List.map` in stdlib	`Iterator::map` (lazy, allocates on `collect`)

//! # List Map from Scratch
//! Deriving `List.map` from scratch — the Abstraction Principle.
//!
//! Three implementations showing how `map` generalises element-by-element
//! list transformation: iterator adapter, explicit recursion, and fold.

/// Iterator-based map: apply `f` to every element and collect.
///
/// This is idiomatic Rust — the standard library's `Iterator::map` does
/// exactly this under the hood, but we call `.collect()` explicitly to
/// mirror the OCaml `'a list -> 'b list` shape.
pub fn map<A, B, F>(list: &[A], f: F) -> Vec<B>
where
    F: Fn(&A) -> B,
{
    list.iter().map(f).collect()
}

/// Recursive map: head-cons pattern mirroring the OCaml definition.
///
/// ```ocaml
/// let rec map f = function
///   | [] -> []
///   | h :: t -> let h' = f h in h' :: map f t
/// ```
pub fn map_recursive<A, B, F>(list: &[A], f: F) -> Vec<B>
where
    F: Fn(&A) -> B,
{
    match list {
        [] => vec![],
        [head, tail @ ..] => {
            let mut result = vec![f(head)];
            result.extend(map_recursive(tail, f));
            result
        }
    }
}

/// Fold-based map: build the result left-to-right with `fold`.
///
/// Demonstrates that `map` is a special case of `fold` where each step
/// appends a transformed element.
pub fn map_fold<A, B, F>(list: &[A], f: F) -> Vec<B>
where
    F: Fn(&A) -> B,
{
    list.iter().fold(Vec::new(), |mut acc, x| {
        acc.push(f(x));
        acc
    })
}

// Partially-applied helpers matching the OCaml `add1`, `to_string`, `double`.

pub fn add1(list: &[i32]) -> Vec<i32> {
    map(list, |x| x + 1)
}

pub fn to_string(list: &[i32]) -> Vec<String> {
    map(list, |x| x.to_string())
}

pub fn double(list: &[i32]) -> Vec<i32> {
    map(list, |x| x * 2)
}

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

    const NUMS: &[i32] = &[1, 2, 3, 4, 5];

    // --- iterator map ---

    #[test]
    fn map_add1() {
        assert_eq!(map(NUMS, |x| x + 1), vec![2, 3, 4, 5, 6]);
    }

    #[test]
    fn map_to_string() {
        assert_eq!(map(NUMS, |x| x.to_string()), vec!["1", "2", "3", "4", "5"]);
    }

    #[test]
    fn map_double() {
        assert_eq!(map(NUMS, |x| x * 2), vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn map_empty() {
        assert_eq!(map::<i32, i32, _>(&[], |x| x + 1), vec![]);
    }

    // --- recursive map ---

    #[test]
    fn map_recursive_add1() {
        assert_eq!(map_recursive(NUMS, |x| x + 1), vec![2, 3, 4, 5, 6]);
    }

    #[test]
    fn map_recursive_double() {
        assert_eq!(map_recursive(NUMS, |x| x * 2), vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn map_recursive_empty() {
        assert_eq!(map_recursive::<i32, i32, _>(&[], |x| x + 1), vec![]);
    }

    // --- fold map ---

    #[test]
    fn map_fold_add1() {
        assert_eq!(map_fold(NUMS, |x| x + 1), vec![2, 3, 4, 5, 6]);
    }

    #[test]
    fn map_fold_double() {
        assert_eq!(map_fold(NUMS, |x| x * 2), vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn map_fold_empty() {
        assert_eq!(map_fold::<i32, i32, _>(&[], |x| x + 1), vec![]);
    }

    // --- helpers ---

    #[test]
    fn helpers_match_ocaml_output() {
        assert_eq!(add1(NUMS), vec![2, 3, 4, 5, 6]);
        assert_eq!(to_string(NUMS), vec!["1", "2", "3", "4", "5"]);
        assert_eq!(double(NUMS), vec![2, 4, 6, 8, 10]);
    }

    // All three implementations must agree
    #[test]
    fn all_implementations_agree() {
        let f = |x: &i32| x * x;
        assert_eq!(map(NUMS, f), map_recursive(NUMS, f));
        assert_eq!(map(NUMS, f), map_fold(NUMS, f));
    }
}

fn main() {
    println!("{:?}", map(NUMS, |x| x + 1), vec![2, 3, 4, 5, 6]);
    println!("{:?}", map(NUMS, |x| x.to_string()), vec!["1", "2", "3", "4", "5"]);
    println!("{:?}", map(NUMS, |x| x * 2), vec![2, 4, 6, 8, 10]);
}

let rec map f = function
  | [] -> []
  | h :: t -> let h' = f h in h' :: map f t

let add1 = map (fun x -> x + 1)
let to_string = map string_of_int
let double = map (fun x -> x * 2)

let () =
  let nums = [1; 2; 3; 4; 5] in
  List.iter (Printf.printf "%d ") (add1 nums); print_newline ();
  List.iter (Printf.printf "%s ") (to_string nums); print_newline ();
  List.iter (Printf.printf "%d ") (double nums); print_newline ()

📊 Detailed Comparison

Comparison: List Map from Scratch

OCaml — recursive definition

🐪 Show OCaml equivalent

let rec map f = function
| [] -> []
| h :: t -> let h' = f h in h' :: map f t

Rust — iterator (idiomatic)

pub fn map<A, B, F: Fn(&A) -> B>(list: &[A], f: F) -> Vec<B> {
 list.iter().map(f).collect()
}

Rust — recursive (mirrors OCaml)

pub fn map_recursive<A, B, F: Fn(&A) -> B>(list: &[A], f: F) -> Vec<B> {
 match list {
     [] => vec![],
     [head, tail @ ..] => {
         let mut result = vec![f(head)];
         result.extend(map_recursive(tail, f));
         result
     }
 }
}

Rust — fold

pub fn map_fold<A, B, F: Fn(&A) -> B>(list: &[A], f: F) -> Vec<B> {
 list.iter().fold(Vec::new(), |mut acc, x| {
     acc.push(f(x));
     acc
 })
}

Partial application comparison

OCaml	Rust
`let add1 = map (fun x -> x + 1)`	`fn add1(list: &[i32]) -> Vec<i32> { map(list, \	x\	x + 1) }`
`let double = map (fun x -> x 2)`	`fn double(list: &[i32]) -> Vec<i32> { map(list, \	x\	x 2) }`
`let to_string = map string_of_int`	`fn to_string(list: &[i32]) -> Vec<String> { map(list, \	x\	x.to_string()) }`

OCaml curries automatically; Rust requires explicit wrapping because `map` takes two arguments rather than returning a closure.

Comparison Table

Aspect	OCaml	Rust
Type signature	`('a -> 'b) -> 'a list -> 'b list`	`fn<A,B,F:Fn(&A)->B>(&[A], F) -> Vec<B>`
Pattern match	`\	[] -> [] \	h :: t -> ...`	`[] => vec![] \	[head, tail @ ..] => ...`
Partial application	Native currying	Closure wrapping
Memory model	GC-managed cons cells	Contiguous `Vec<B>` on heap
Tail recursion	Not tail-recursive (OCaml TCO not applied here)	Not tail-recursive (use iterator version)
Idiomatic style	Recursive with pattern match	`iter().map().collect()`

Takeaways

`map` is the canonical abstraction for element-wise list transformation
Rust's iterator `map` adapter and OCaml's `List.map` have the same semantics; both are lazy/eager respectively
The recursive Rust version uses slice patterns (`[head, tail @ ..]`) which are the closest structural analogue to OCaml's cons patterns
Fold proves `map` is a specialisation: every `map` can be rewritten as a `fold`