1121 Intermediate

1121-listmap-transform-every-element — List.map: Transform Every Element

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "1121-listmap-transform-every-element — List.map: Transform Every Element" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. `map` is the fundamental operation of functional programming: apply a function to every element of a list, producing a new list of the same length with transformed values. Key difference from OCaml: 1. **Laziness**: Rust's `Iterator::map` is lazy — the function runs only when elements are consumed; OCaml's `List.map` is strict — all elements are transformed immediately.

Tutorial

The Problem

map is the fundamental operation of functional programming: apply a function to every element of a list, producing a new list of the same length with transformed values. It is the backbone of data transformation pipelines, API response formatting, and mathematical vector operations.

OCaml's List.map and Rust's Iterator::map both express this transformation, but with different evaluation strategies: OCaml's list is strict and builds a new linked list, while Rust's iterator is lazy and computes values on demand.

🎯 Learning Outcomes

• Use Iterator::map to transform a slice into a new Vec

• Implement recursive map mirroring OCaml's List.map structure

• Understand the difference between strict list map and lazy iterator map

• Recognize map as the functor operation for lists

• Apply map in data transformation pipelines with .collect()

Code Example

pub fn map_idiomatic<F, T, U>(list: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    list.iter().map(f).collect()
}

let numbers = [1; 2; 3; 4; 5]
let doubled = List.map (fun x -> x * 2) numbers
let () = List.iter (fun x -> Printf.printf "%d " x) doubled
(* Output: 2 4 6 8 10 *)

(* More general: define a map function ourselves *)
let rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs

let () =
  assert (map (fun x -> x * 2) [1;2;3;4;5] = [2;4;6;8;10])

Key Differences

Laziness: Rust's Iterator::map is lazy — the function runs only when elements are consumed; OCaml's List.map is strict — all elements are transformed immediately.

Allocation: Rust's .collect() allocates the result Vec in one pass; OCaml's List.map allocates one cons cell per element.

Slice vs list: Rust operates on contiguous slices with random access; OCaml's List.map traverses a linked list sequentially.

Type inference: Both infer the type of f from usage — map(|x| x * 2) works without type annotations in both.

OCaml Approach

let rec map f = function
  | [] -> []
  | x :: rest -> f x :: map f rest

OCaml's built-in List.map uses this exact structure. It builds the new list from right to left via recursion (not tail-recursive) or from left to right in tail-recursive form with List.rev.

Full Source

#![allow(clippy::all)]
//! List.map — Transform Every Element
//!
//! Apply a function to each element of a list.

/// Idiomatic Rust: use iterators and map.
pub fn map_idiomatic<F, T, U>(list: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    list.iter().map(f).collect()
}

/// Recursive implementation: similar to OCaml's List.map.
pub fn map_recursive<F, T, U>(list: &[T], f: &F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    match list {
        [] => vec![],
        [head, tail @ ..] => {
            let mut result = vec![f(head)];
            result.extend(map_recursive(tail, f));
            result
        }
    }
}

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

    #[test]
    fn test_empty() {
        let empty: Vec<i32> = vec![];
        let result = map_idiomatic(&empty, |x| x * 2);
        assert_eq!(result, vec![]);
        let result2 = map_recursive(&empty, &|x| x * 2);
        assert_eq!(result2, vec![]);
    }

    #[test]
    fn test_single() {
        let list = vec![1];
        let result = map_idiomatic(&list, |x| x * 2);
        assert_eq!(result, vec![2]);
        let result2 = map_recursive(&list, &|x| x * 2);
        assert_eq!(result2, vec![2]);
    }

    #[test]
    fn test_multiple() {
        let list = vec![1, 2, 3, 4, 5];
        let result = map_idiomatic(&list, |x| x * 2);
        assert_eq!(result, vec![2, 4, 6, 8, 10]);
        let result2 = map_recursive(&list, &|x| x * 2);
        assert_eq!(result2, vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn test_strings() {
        let list = vec!["a", "bb", "ccc"];
        let result = map_idiomatic(&list, |s| s.len());
        assert_eq!(result, vec![1, 2, 3]);
        let result2 = map_recursive(&list, &|s| s.len());
        assert_eq!(result2, vec![1, 2, 3]);
    }
}

let numbers = [1; 2; 3; 4; 5]
let doubled = List.map (fun x -> x * 2) numbers
let () = List.iter (fun x -> Printf.printf "%d " x) doubled
(* Output: 2 4 6 8 10 *)

✓ Tests Rust test suite

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

    #[test]
    fn test_empty() {
        let empty: Vec<i32> = vec![];
        let result = map_idiomatic(&empty, |x| x * 2);
        assert_eq!(result, vec![]);
        let result2 = map_recursive(&empty, &|x| x * 2);
        assert_eq!(result2, vec![]);
    }

    #[test]
    fn test_single() {
        let list = vec![1];
        let result = map_idiomatic(&list, |x| x * 2);
        assert_eq!(result, vec![2]);
        let result2 = map_recursive(&list, &|x| x * 2);
        assert_eq!(result2, vec![2]);
    }

    #[test]
    fn test_multiple() {
        let list = vec![1, 2, 3, 4, 5];
        let result = map_idiomatic(&list, |x| x * 2);
        assert_eq!(result, vec![2, 4, 6, 8, 10]);
        let result2 = map_recursive(&list, &|x| x * 2);
        assert_eq!(result2, vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn test_strings() {
        let list = vec!["a", "bb", "ccc"];
        let result = map_idiomatic(&list, |s| s.len());
        assert_eq!(result, vec![1, 2, 3]);
        let result2 = map_recursive(&list, &|s| s.len());
        assert_eq!(result2, vec![1, 2, 3]);
    }
}

Deep Comparison

OCaml vs Rust: List.map — Transform Every Element

Side-by-Side Code

OCaml

let numbers = [1; 2; 3; 4; 5]
let doubled = List.map (fun x -> x * 2) numbers
let () = List.iter (fun x -> Printf.printf "%d " x) doubled
(* Output: 2 4 6 8 10 *)

(* More general: define a map function ourselves *)
let rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs

let () =
  assert (map (fun x -> x * 2) [1;2;3;4;5] = [2;4;6;8;10])

Rust (idiomatic)

pub fn map_idiomatic<F, T, U>(list: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    list.iter().map(f).collect()
}

Rust (functional/recursive)

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

Type Signatures

Concept	OCaml	Rust
Function signature	`val map : ('a -> 'b) -> 'a list -> 'b list`	`fn map_idiomatic<F, T, U>(list: &[T], f: F) -> Vec<U>`
List type	`'a list` (linked list)	`&[T]` (slice) / `Vec<T>` (owned vector)
Higher-order function	First-class functions, closures	Closures implementing `Fn`, `FnMut`, `FnOnce`
Return type	New list allocated	New `Vec<U>` allocated (owned)

Key Insights

Ownership and Borrowing: In Rust, the input list is borrowed as a slice (&[T]), which does not take ownership. The output is a new owned Vec<U>. This is similar to OCaml's functional style where the input list is immutable and a new list is returned.

Type System: Rust requires explicit generic bounds (F: Fn(&T) -> U) to ensure the closure can be called. OCaml's type inference automatically deduces the function type.

Performance: Rust's iterator-based map is zero-cost abstraction and can be highly optimized. The recursive version is less efficient due to repeated allocations and recursion depth limits, but mirrors OCaml's recursion pattern.

Pattern Matching: Both languages support pattern matching for recursive decomposition. Rust's slice patterns ([head, tail @ ..]) are similar to OCaml's x :: xs.

Mutability: The idiomatic Rust version uses immutable borrows and produces a new vector. The recursive version also avoids mutation inside the recursion (except for building the result vector via extend). OCaml's lists are immutable by default.

When to Use Each Style

Use idiomatic Rust when: You are working with slices or iterators and want maximum performance and readability. The iterator chain list.iter().map(f).collect() is the standard Rust idiom and is immediately recognizable to Rust developers.

Use recursive Rust when: You are teaching functional programming concepts, comparing directly with OCaml, or need to mirror a recursive algorithm that doesn't fit well into iterators (e.g., tree traversal). Recursive Rust can be clearer for certain algorithms but may suffer from stack overflow for large inputs (unlike OCaml's tail‑call optimization).

Exercises

Implement map_with_index<F: Fn(usize, &T) -> U>(list: &[T], f: F) -> Vec<U> that passes the index along with each element.

Write flat_map<F: Fn(&T) -> Vec<U>>(list: &[T], f: F) -> Vec<U> that maps and flattens (equivalent to OCaml's List.concat_map).

Implement map_in_place<T, F: Fn(&mut T)>(list: &mut [T], f: F) that transforms elements without allocating a new collection.

Open Source Repos

functional-rust

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

Rust