942 Fundamental

942 Matrix Operations

Functional Programming

Tutorial

The Problem

Implement functional matrix operations — transpose, dot product, matrix multiplication, and scalar scaling — using nested iterators. The goal is to represent matrices as Vec<Vec<i64>> and express all operations as iterator pipelines, mirroring OCaml's style of computing on immutable nested lists. Avoid explicit index mutation; derive matrix multiply from transpose and dot product.

🎯 Learning Outcomes

• Represent a 2D matrix as Vec<Vec<i64>> (type alias Matrix) and iterate over rows and columns

• Implement transpose by column extraction: (0..cols).map(|col| matrix.iter().map(|row| row[col]).collect())

• Implement dot product using .zip().map().sum() — no manual index loops

• Derive multiply(A, B) as A.rows × B^T.rows via nested map + dot

• Implement scalar scale with nested map

Code Example

#![allow(clippy::all)]
/// # Matrix Operations — Functional 2D
///
/// Matrix transpose and multiply using nested Vecs.
/// Demonstrates nested iteration patterns and borrowing with 2D structures.

pub type Matrix = Vec<Vec<i64>>;

/// Transpose: swap rows and columns.
/// Uses iterator-based column extraction.
pub fn transpose(matrix: &Matrix) -> Matrix {
    if matrix.is_empty() || matrix[0].is_empty() {
        return vec![];
    }
    let cols = matrix[0].len();
    (0..cols)
        .map(|col| matrix.iter().map(|row| row[col]).collect())
        .collect()
}

/// Dot product of two vectors.
pub fn dot(a: &[i64], b: &[i64]) -> i64 {
    a.iter().zip(b.iter()).map(|(x, y)| x * y).sum()
}

/// Matrix multiplication: A(m×n) × B(n×p) = C(m×p)
pub fn multiply(a: &Matrix, b: &Matrix) -> Matrix {
    let bt = transpose(b);
    a.iter()
        .map(|row| bt.iter().map(|col| dot(row, col)).collect())
        .collect()
}

/// Scalar multiplication
pub fn scale(matrix: &Matrix, scalar: i64) -> Matrix {
    matrix
        .iter()
        .map(|row| row.iter().map(|&x| x * scalar).collect())
        .collect()
}

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

    #[test]
    fn test_transpose() {
        let m = vec![vec![1, 2, 3], vec![4, 5, 6]];
        assert_eq!(transpose(&m), vec![vec![1, 4], vec![2, 5], vec![3, 6]]);
    }

    #[test]
    fn test_transpose_empty() {
        let m: Matrix = vec![];
        assert_eq!(transpose(&m), vec![] as Matrix);
    }

    #[test]
    fn test_dot() {
        assert_eq!(dot(&[1, 2, 3], &[4, 5, 6]), 32);
    }

    #[test]
    fn test_multiply() {
        let a = vec![vec![1, 2, 3], vec![4, 5, 6]];
        let b = vec![vec![7, 8], vec![9, 10], vec![11, 12]];
        assert_eq!(multiply(&a, &b), vec![vec![58, 64], vec![139, 154]]);
    }

    #[test]
    fn test_scale() {
        let m = vec![vec![1, 2], vec![3, 4]];
        assert_eq!(scale(&m, 3), vec![vec![3, 6], vec![9, 12]]);
    }

    #[test]
    fn test_identity_multiply() {
        let a = vec![vec![1, 2], vec![3, 4]];
        let id = vec![vec![1, 0], vec![0, 1]];
        assert_eq!(multiply(&a, &id), a);
    }
}

(* Matrix Operations — Functional 2D *)

let transpose matrix =
  match matrix with
  | [] -> []
  | _ -> List.init (List.length (List.hd matrix)) (fun i ->
    List.map (fun row -> List.nth row i) matrix)

let dot a b = List.fold_left2 (fun acc x y -> acc + x * y) 0 a b

let multiply a b =
  let bt = transpose b in
  List.map (fun row -> List.map (dot row) bt) a

let print_matrix m =
  List.iter (fun row ->
    List.iter (Printf.printf "%3d ") row;
    print_newline ()
  ) m

let () =
  let a = [[1;2;3];[4;5;6]] in
  let b = [[7;8];[9;10];[11;12]] in
  print_matrix (multiply a b);
  assert (multiply a b = [[58;64];[139;154]]);
  Printf.printf "Matrix tests passed!\n"

Key Differences

Aspect	Rust	OCaml
Matrix type	`Vec<Vec<i64>>` — heap-allocated, O(1) index access	`int list list` — linked lists, O(n) `List.nth`
Column extraction	`row[col]` — O(1)	`List.nth row col` — O(n)
Nested map	`.map(\|row\| .map(\|col\| ...))`	`List.map (List.map ...)`
Partial application	Closure required: `move \|x\| x * s`	`(( * ) s)` — natural currying
Performance	Cache-friendly for row-major access	Poor cache behavior due to linked list pointers

For performance-critical matrix work, ndarray or nalgebra crates are preferred over Vec<Vec<T>>. The functional style shown here prioritizes clarity and correctness over performance.

OCaml Approach

let transpose = function
  | [] -> []
  | [] :: _ -> []
  | rows ->
    let ncols = List.length (List.hd rows) in
    List.init ncols (fun col ->
      List.map (fun row -> List.nth row col) rows)

let dot a b =
  List.fold_left2 (fun acc x y -> acc + x * y) 0 a b

let multiply a b =
  let bt = transpose b in
  List.map (fun row ->
    List.map (fun col -> dot row col) bt
  ) a

let scale s m =
  List.map (List.map (( * ) s)) m

OCaml's List.map (List.map ...) idiom is extremely concise for nested operations. The scale function using (( * ) s) is a partial application of multiplication — even more compact than Rust's closure syntax.

Full Source

#![allow(clippy::all)]
/// # Matrix Operations — Functional 2D
///
/// Matrix transpose and multiply using nested Vecs.
/// Demonstrates nested iteration patterns and borrowing with 2D structures.

pub type Matrix = Vec<Vec<i64>>;

/// Transpose: swap rows and columns.
/// Uses iterator-based column extraction.
pub fn transpose(matrix: &Matrix) -> Matrix {
    if matrix.is_empty() || matrix[0].is_empty() {
        return vec![];
    }
    let cols = matrix[0].len();
    (0..cols)
        .map(|col| matrix.iter().map(|row| row[col]).collect())
        .collect()
}

/// Dot product of two vectors.
pub fn dot(a: &[i64], b: &[i64]) -> i64 {
    a.iter().zip(b.iter()).map(|(x, y)| x * y).sum()
}

/// Matrix multiplication: A(m×n) × B(n×p) = C(m×p)
pub fn multiply(a: &Matrix, b: &Matrix) -> Matrix {
    let bt = transpose(b);
    a.iter()
        .map(|row| bt.iter().map(|col| dot(row, col)).collect())
        .collect()
}

/// Scalar multiplication
pub fn scale(matrix: &Matrix, scalar: i64) -> Matrix {
    matrix
        .iter()
        .map(|row| row.iter().map(|&x| x * scalar).collect())
        .collect()
}

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

    #[test]
    fn test_transpose() {
        let m = vec![vec![1, 2, 3], vec![4, 5, 6]];
        assert_eq!(transpose(&m), vec![vec![1, 4], vec![2, 5], vec![3, 6]]);
    }

    #[test]
    fn test_transpose_empty() {
        let m: Matrix = vec![];
        assert_eq!(transpose(&m), vec![] as Matrix);
    }

    #[test]
    fn test_dot() {
        assert_eq!(dot(&[1, 2, 3], &[4, 5, 6]), 32);
    }

    #[test]
    fn test_multiply() {
        let a = vec![vec![1, 2, 3], vec![4, 5, 6]];
        let b = vec![vec![7, 8], vec![9, 10], vec![11, 12]];
        assert_eq!(multiply(&a, &b), vec![vec![58, 64], vec![139, 154]]);
    }

    #[test]
    fn test_scale() {
        let m = vec![vec![1, 2], vec![3, 4]];
        assert_eq!(scale(&m, 3), vec![vec![3, 6], vec![9, 12]]);
    }

    #[test]
    fn test_identity_multiply() {
        let a = vec![vec![1, 2], vec![3, 4]];
        let id = vec![vec![1, 0], vec![0, 1]];
        assert_eq!(multiply(&a, &id), a);
    }
}

(* Matrix Operations — Functional 2D *)

let transpose matrix =
  match matrix with
  | [] -> []
  | _ -> List.init (List.length (List.hd matrix)) (fun i ->
    List.map (fun row -> List.nth row i) matrix)

let dot a b = List.fold_left2 (fun acc x y -> acc + x * y) 0 a b

let multiply a b =
  let bt = transpose b in
  List.map (fun row -> List.map (dot row) bt) a

let print_matrix m =
  List.iter (fun row ->
    List.iter (Printf.printf "%3d ") row;
    print_newline ()
  ) m

let () =
  let a = [[1;2;3];[4;5;6]] in
  let b = [[7;8];[9;10];[11;12]] in
  print_matrix (multiply a b);
  assert (multiply a b = [[58;64];[139;154]]);
  Printf.printf "Matrix tests passed!\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_transpose() {
        let m = vec![vec![1, 2, 3], vec![4, 5, 6]];
        assert_eq!(transpose(&m), vec![vec![1, 4], vec![2, 5], vec![3, 6]]);
    }

    #[test]
    fn test_transpose_empty() {
        let m: Matrix = vec![];
        assert_eq!(transpose(&m), vec![] as Matrix);
    }

    #[test]
    fn test_dot() {
        assert_eq!(dot(&[1, 2, 3], &[4, 5, 6]), 32);
    }

    #[test]
    fn test_multiply() {
        let a = vec![vec![1, 2, 3], vec![4, 5, 6]];
        let b = vec![vec![7, 8], vec![9, 10], vec![11, 12]];
        assert_eq!(multiply(&a, &b), vec![vec![58, 64], vec![139, 154]]);
    }

    #[test]
    fn test_scale() {
        let m = vec![vec![1, 2], vec![3, 4]];
        assert_eq!(scale(&m, 3), vec![vec![3, 6], vec![9, 12]]);
    }

    #[test]
    fn test_identity_multiply() {
        let a = vec![vec![1, 2], vec![3, 4]];
        let id = vec![vec![1, 0], vec![0, 1]];
        assert_eq!(multiply(&a, &id), a);
    }
}

Deep Comparison

Matrix Operations — OCaml vs Rust Comparison

Core Insight

Both languages represent matrices as nested lists/vectors. OCaml's List.map and List.fold_left2 provide elegant functional matrix operations. Rust's iter().zip().map().sum() is equally clean but operates on contiguous memory rather than linked lists — a significant performance advantage for numeric work.

OCaml Approach

Matrices are int list list. Transpose uses List.init with List.nth (O(n) per access — not ideal for large matrices). Dot product uses List.fold_left2 which zips and folds simultaneously. Clean and readable but O(n²) memory access patterns due to linked lists.

Rust Approach

Matrices are Vec<Vec<i64>>. Transpose uses range-based column iteration. Dot product uses iter().zip().map().sum() — a zero-allocation iterator chain. All data is contiguous in memory, making this cache-friendly. Borrows (&Matrix) ensure the input isn't consumed.

Comparison Table

Aspect	OCaml	Rust
Memory	Linked lists (scattered)	Vec<Vec> (contiguous rows)
Null safety	N/A	N/A
Errors	Index out of bounds	Panic on OOB (or use `.get()`)
Iteration	`List.map` + `List.nth`	`iter().zip().map().sum()`
Performance	O(n) per element access	O(1) per element access

Things Rust Learners Should Notice

**&Matrix borrows** — functions take references, don't consume the input

**zip() + map() + sum()** — the idiomatic dot product pattern, zero allocation

**collect::<Vec<_>>()** — type annotation drives the output collection type

Cache locality — Vec<Vec<i64>> keeps each row contiguous; huge perf win over linked lists

Type alias — type Matrix = Vec<Vec<i64>> keeps signatures readable

Exercises

Add add_matrices(a, b) that element-wise sums two matrices of equal dimensions.

Implement identity_matrix(n) that generates an n×n identity matrix using (0..n).map(...).

Write a matrix power function pow(m, n) using repeated multiplication.

Implement trace(m) — the sum of diagonal elements — using enumerate.

Verify that multiply(A, identity(n)) == A and transpose(transpose(A)) == A in tests.

Open Source Repos

functional-rust

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

Rust

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Matrix Operations — OCaml vs Rust Comparison

Core Insight

OCaml Approach

Rust Approach

Comparison Table

Things Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos