077 Intermediate

077 — Matrix Operations

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "077 — Matrix Operations" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Matrix operations — transpose and multiplication — are the foundation of linear algebra, which underpins graphics (rotation/scaling transforms), machine learning (neural network layers are matrix multiplications), physics simulation (finite element methods), and signal processing (FFT as matrix multiplication). Key difference from OCaml: 1. **`List.nth` is O(n)**: OCaml's list

Tutorial

The Problem

Matrix operations — transpose and multiplication — are the foundation of linear algebra, which underpins graphics (rotation/scaling transforms), machine learning (neural network layers are matrix multiplications), physics simulation (finite element methods), and signal processing (FFT as matrix multiplication). Understanding the data layout and functional implementation of these operations is prerequisite for any numerical computing work.

The functional approach: transpose by column extraction with iterators; multiply by dot products of rows and columns. The ownership model for matrices in Rust — take ownership for consuming operations, borrow for non-consuming ones — illustrates the practical impact of ownership on API design.

🎯 Learning Outcomes

• Transpose a matrix using iterator-based column extraction

• Multiply matrices using dot products of rows and transposed columns

• Understand why transpose is taken before multiplication (column access)

• Use (0..cols).map(|c| (0..rows).map(|r| matrix[r][c]).collect()) for functional transpose

• Design APIs that take ownership vs borrow based on whether they consume the matrix

Code Example

#![allow(clippy::all)]
/// Matrix operations using Vec<Vec<i64>>
///
/// Ownership insight: Matrices are heap-allocated Vec<Vec<i64>>.
/// Transpose and multiply consume or borrow the input matrices.

/// Transpose a matrix — takes ownership, returns new matrix
pub fn transpose(matrix: Vec<Vec<i64>>) -> Vec<Vec<i64>> {
    if matrix.is_empty() || matrix[0].is_empty() {
        return vec![];
    }
    let rows = matrix.len();
    let cols = matrix[0].len();
    (0..cols)
        .map(|c| (0..rows).map(|r| matrix[r][c]).collect())
        .collect()
}

/// Transpose by reference — borrows input
pub fn transpose_ref(matrix: &[Vec<i64>]) -> Vec<Vec<i64>> {
    if matrix.is_empty() || matrix[0].is_empty() {
        return vec![];
    }
    let cols = matrix[0].len();
    (0..cols)
        .map(|c| matrix.iter().map(|row| row[c]).collect())
        .collect()
}

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

/// Matrix multiplication
pub fn multiply(a: &[Vec<i64>], b: &[Vec<i64>]) -> Vec<Vec<i64>> {
    let bt = transpose_ref(b);
    a.iter()
        .map(|row| bt.iter().map(|col| dot(row, col)).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: Vec<Vec<i64>> = vec![];
        assert_eq!(transpose(m), Vec::<Vec<i64>>::new());
    }

    #[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_transpose_ref() {
        let m = vec![vec![1, 2], vec![3, 4]];
        assert_eq!(transpose_ref(&m), vec![vec![1, 3], vec![2, 4]]);
    }

    #[test]
    fn test_identity_multiply() {
        let a = vec![vec![1, 0], vec![0, 1]];
        let b = vec![vec![5, 6], vec![7, 8]];
        assert_eq!(multiply(&a, &b), b);
    }
}

(* Matrix Operations — Functional 2D *)

(* Version 1: Transpose using List.init and List.nth *)
let transpose matrix =
  match matrix with
  | [] -> []
  | _ -> List.init (List.length (List.hd matrix)) (fun i ->
    List.map (fun row -> List.nth row i) matrix)

(* Version 2: Dot product and matrix multiply *)
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 () =
  let a = [[1;2;3];[4;5;6]] in
  let b = [[7;8];[9;10];[11;12]] in
  let r = multiply a b in
  assert (r = [[58;64];[139;154]])

Key Differences

**List.nth is O(n)**: OCaml's list-based matrix has O(n·m) access patterns due to List.nth. Use Array.make_matrix for O(1) random access. Rust's Vec<Vec<i64>> has O(1) indexed access.

Ownership in API: transpose(matrix: Vec<Vec<i64>>) moves the matrix — useful when you do not need the original. transpose_ref(&[Vec<i64>]) borrows — useful when the original is still needed.

Cache efficiency: Vec<Vec<i64>> is not contiguous in memory (each row is separately allocated). For high-performance matrix operations, use a flat Vec<i64> with manual indexing or ndarray crate.

**zip + sum for dot product**: a.iter().zip(b.iter()).map(|(x, y)| x * y).sum() is the idiomatic Rust dot product. OCaml's List.fold_left2 (+) 0 row col is equivalent.

OCaml Approach

OCaml's list-based transpose and multiply:

let transpose m =
  let rows = List.length m in
  let cols = List.length (List.hd m) in
  List.init cols (fun c ->
    List.init rows (fun r ->
      List.nth (List.nth m r) c))  (* O(n) per access *)

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

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

For performance, use Array.make_matrix (O(1) random access). OCaml's Bigarray provides flat contiguous storage equivalent to ndarray in Rust.

Full Source

#![allow(clippy::all)]
/// Matrix operations using Vec<Vec<i64>>
///
/// Ownership insight: Matrices are heap-allocated Vec<Vec<i64>>.
/// Transpose and multiply consume or borrow the input matrices.

/// Transpose a matrix — takes ownership, returns new matrix
pub fn transpose(matrix: Vec<Vec<i64>>) -> Vec<Vec<i64>> {
    if matrix.is_empty() || matrix[0].is_empty() {
        return vec![];
    }
    let rows = matrix.len();
    let cols = matrix[0].len();
    (0..cols)
        .map(|c| (0..rows).map(|r| matrix[r][c]).collect())
        .collect()
}

/// Transpose by reference — borrows input
pub fn transpose_ref(matrix: &[Vec<i64>]) -> Vec<Vec<i64>> {
    if matrix.is_empty() || matrix[0].is_empty() {
        return vec![];
    }
    let cols = matrix[0].len();
    (0..cols)
        .map(|c| matrix.iter().map(|row| row[c]).collect())
        .collect()
}

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

/// Matrix multiplication
pub fn multiply(a: &[Vec<i64>], b: &[Vec<i64>]) -> Vec<Vec<i64>> {
    let bt = transpose_ref(b);
    a.iter()
        .map(|row| bt.iter().map(|col| dot(row, col)).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: Vec<Vec<i64>> = vec![];
        assert_eq!(transpose(m), Vec::<Vec<i64>>::new());
    }

    #[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_transpose_ref() {
        let m = vec![vec![1, 2], vec![3, 4]];
        assert_eq!(transpose_ref(&m), vec![vec![1, 3], vec![2, 4]]);
    }

    #[test]
    fn test_identity_multiply() {
        let a = vec![vec![1, 0], vec![0, 1]];
        let b = vec![vec![5, 6], vec![7, 8]];
        assert_eq!(multiply(&a, &b), b);
    }
}

(* Matrix Operations — Functional 2D *)

(* Version 1: Transpose using List.init and List.nth *)
let transpose matrix =
  match matrix with
  | [] -> []
  | _ -> List.init (List.length (List.hd matrix)) (fun i ->
    List.map (fun row -> List.nth row i) matrix)

(* Version 2: Dot product and matrix multiply *)
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 () =
  let a = [[1;2;3];[4;5;6]] in
  let b = [[7;8];[9;10];[11;12]] in
  let r = multiply a b in
  assert (r = [[58;64];[139;154]])

✓ 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: Vec<Vec<i64>> = vec![];
        assert_eq!(transpose(m), Vec::<Vec<i64>>::new());
    }

    #[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_transpose_ref() {
        let m = vec![vec![1, 2], vec![3, 4]];
        assert_eq!(transpose_ref(&m), vec![vec![1, 3], vec![2, 4]]);
    }

    #[test]
    fn test_identity_multiply() {
        let a = vec![vec![1, 0], vec![0, 1]];
        let b = vec![vec![5, 6], vec![7, 8]];
        assert_eq!(multiply(&a, &b), b);
    }
}

Deep Comparison

Matrix Operations — Comparison

Core Insight

Matrix operations reveal the difference between OCaml's persistent lists (shared by default) and Rust's owned vectors (moved by default). Transpose in OCaml creates new lists sharing structure; in Rust you must choose between consuming the input or borrowing it.

OCaml Approach

• Nested lists int list list — immutable, GC-managed

• List.init + List.nth for transpose (O(n²) access)

• List.fold_left2 elegantly zips and accumulates dot product

• No concern about who "owns" the matrix

Rust Approach

• Vec<Vec<i64>> — heap-allocated, owned

• Two transpose variants: one takes ownership, one borrows with &[Vec<i64>]

• Iterator chains with .map(), .zip(), .sum()

• Must decide: does multiply consume or borrow inputs?

Comparison Table

Aspect	OCaml	Rust
Collection	`int list list`	`Vec<Vec<i64>>`
Access	`List.nth` O(n)	Index `[i]` O(1)
Ownership	GC shared	Move or borrow
Zip+fold	`fold_left2`	`.zip().map().sum()`
Transpose	Always new list	Can consume or borrow

Learner Notes

• Rust slices &[Vec<i64>] let you borrow without ownership transfer

• .iter().map().collect() is the Rust equivalent of List.map

• OCaml List.nth is O(n); Rust indexing is O(1) — different performance profile

• Consider using a flat Vec<i64> with stride for real matrix work

Exercises

Strassen's algorithm: Implement Strassen's O(n^2.807) matrix multiplication for 2x2 matrices and verify it produces the same result as naive multiplication.

Identity check: Write is_identity(m: &[Vec<i64>]) -> bool that checks if a matrix is the identity matrix. What are the conditions?

Matrix power: Write mat_pow(m: &[Vec<i64>], n: u32) -> Vec<Vec<i64>> using fast exponentiation (squaring). Verify mat_pow([[1,1],[1,0]], n) gives Fibonacci numbers.

Open Source Repos

functional-rust

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

Rust