279 Fundamental

Pascal's Triangle — Row Generation

Math/Recursion

Tutorial Video

Text description (accessibility)

This video demonstrates the "Pascal's Triangle — Row Generation" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Math/Recursion. Generate the first N rows of Pascal's triangle, where each row is computed from the previous one using the "zip-with-add" trick: prepend and append 0 to the current row, then sum pairwise. Key difference from OCaml: 1. **Zip

Tutorial

The Problem

Generate the first N rows of Pascal's triangle, where each row is computed from the previous one using the "zip-with-add" trick: prepend and append 0 to the current row, then sum pairwise.

🎯 Learning Outcomes

• Using std::iter::successors for generating sequences from a recurrence

• Iterator chaining with once, chain, and zip to implement zip-with-add

• Translating OCaml's List.map2 to Rust's iterator zip pattern

• Comparing recursive, fold, and successors approaches

🦀 The Rust Way

Rust uses std::iter::once(&0).chain(row.iter()).zip(row.iter().chain(once(&0))) — the same prepend/append-zero trick expressed with iterator adapters. std::iter::successors generates the infinite sequence of rows lazily, and .take(n) limits it.

Code Example

pub fn next_row(row: &[u64]) -> Vec<u64> {
    std::iter::once(&0)
        .chain(row.iter())
        .zip(row.iter().chain(std::iter::once(&0)))
        .map(|(a, b)| a + b)
        .collect()
}

pub fn pascal(n: usize) -> Vec<Vec<u64>> {
    std::iter::successors(Some(vec![1u64]), |prev| Some(next_row(prev)))
        .take(n)
        .collect()
}

let next_row row =
  List.map2 (+) (0 :: row) (row @ [0])

let pascal n =
  let rec go row i =
    if i > n then []
    else row :: go (next_row row) (i + 1)
  in go [1] 1

Key Differences

Zip-with-add: OCaml's List.map2 (+) is a single call; Rust chains once, chain, zip, and map — more verbose but composable

Sequence generation: OCaml uses explicit recursion (let rec go); Rust's successors provides a declarative "generate from seed" pattern

Lazy vs eager: Rust's successors is lazy — rows are only computed when consumed; OCaml's recursion eagerly builds the full list

Numeric type: OCaml uses arbitrary-precision int; Rust uses u64 which can overflow for large row numbers

OCaml Approach

OCaml uses List.map2 (+) to add two lists element-wise. The trick: 0 :: row prepends a zero, row @ [0] appends a zero, making both lists the same length. List.map2 (+) then sums corresponding elements to produce the next row. Recursion accumulates rows.

Full Source

#![allow(clippy::all)]
/// Generate the next row of Pascal's triangle from the current row.
///
/// Uses the "zip-with-add" trick: prepend 0 to the row, append 0 to the row,
/// then add corresponding elements pairwise.
///
/// OCaml: `List.map2 (+) (0 :: row) (row @ [0])`
/// Rust:  zip two iterators with offset and sum
pub fn next_row(row: &[u64]) -> Vec<u64> {
    // [0, a, b, c] zipped with [a, b, c, 0] → [a, a+b, b+c, c]
    std::iter::once(&0)
        .chain(row.iter())
        .zip(row.iter().chain(std::iter::once(&0)))
        .map(|(a, b)| a + b)
        .collect()
}

/// Generate `n` rows of Pascal's triangle.
///
/// # Idiomatic Rust — iterative with successors
pub fn pascal(n: usize) -> Vec<Vec<u64>> {
    std::iter::successors(Some(vec![1u64]), |prev| Some(next_row(prev)))
        .take(n)
        .collect()
}

/// Recursive version — mirrors OCaml's `let rec go`.
pub fn pascal_recursive(n: usize) -> Vec<Vec<u64>> {
    fn go(row: Vec<u64>, i: usize, n: usize) -> Vec<Vec<u64>> {
        if i > n {
            return Vec::new();
        }
        let next = next_row(&row);
        let mut result = vec![row];
        result.extend(go(next, i + 1, n));
        result
    }
    if n == 0 {
        return Vec::new();
    }
    go(vec![1], 1, n)
}

/// Fold-based version — accumulates rows by folding over a range.
pub fn pascal_fold(n: usize) -> Vec<Vec<u64>> {
    if n == 0 {
        return Vec::new();
    }
    let (rows, _) = (1..n).fold((vec![vec![1u64]], vec![1u64]), |(mut rows, prev), _| {
        let next = next_row(&prev);
        rows.push(next.clone());
        (rows, next)
    });
    rows
}

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

    #[test]
    fn test_empty() {
        assert!(pascal(0).is_empty());
    }

    #[test]
    fn test_single_row() {
        assert_eq!(pascal(1), vec![vec![1]]);
    }

    #[test]
    fn test_five_rows() {
        let expected = vec![
            vec![1],
            vec![1, 1],
            vec![1, 2, 1],
            vec![1, 3, 3, 1],
            vec![1, 4, 6, 4, 1],
        ];
        assert_eq!(pascal(5), expected);
    }

    #[test]
    fn test_eight_rows() {
        let rows = pascal(8);
        assert_eq!(rows.len(), 8);
        // Row 7 (0-indexed) should be [1, 7, 21, 35, 35, 21, 7, 1]
        assert_eq!(rows[7], vec![1, 7, 21, 35, 35, 21, 7, 1]);
    }

    #[test]
    fn test_row_symmetry() {
        let rows = pascal(10);
        for row in &rows {
            let reversed: Vec<u64> = row.iter().rev().copied().collect();
            assert_eq!(row, &reversed);
        }
    }

    #[test]
    fn test_next_row() {
        assert_eq!(next_row(&[1]), vec![1, 1]);
        assert_eq!(next_row(&[1, 1]), vec![1, 2, 1]);
        assert_eq!(next_row(&[1, 2, 1]), vec![1, 3, 3, 1]);
    }

    #[test]
    fn test_recursive_matches_iterative() {
        for n in 0..10 {
            assert_eq!(pascal(n), pascal_recursive(n), "Mismatch at n={}", n);
        }
    }

    #[test]
    fn test_fold_matches_iterative() {
        for n in 0..10 {
            assert_eq!(pascal(n), pascal_fold(n), "Fold mismatch at n={}", n);
        }
    }
}

let next_row row =
  List.map2 (+) (0 :: row) (row @ [0])

let pascal n =
  let rec go row i =
    if i > n then []
    else row :: go (next_row row) (i + 1)
  in go [1] 1

let () =
  pascal 8 |> List.iter (fun row ->
    List.iter (Printf.printf "%d ") row;
    print_newline ()
  );
  (* Assertions *)
  assert (next_row [1] = [1; 1]);
  assert (next_row [1; 1] = [1; 2; 1]);
  assert (List.length (pascal 8) = 8);
  let row7 = List.nth (pascal 8) 7 in
  assert (row7 = [1; 7; 21; 35; 35; 21; 7; 1]);
  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_empty() {
        assert!(pascal(0).is_empty());
    }

    #[test]
    fn test_single_row() {
        assert_eq!(pascal(1), vec![vec![1]]);
    }

    #[test]
    fn test_five_rows() {
        let expected = vec![
            vec![1],
            vec![1, 1],
            vec![1, 2, 1],
            vec![1, 3, 3, 1],
            vec![1, 4, 6, 4, 1],
        ];
        assert_eq!(pascal(5), expected);
    }

    #[test]
    fn test_eight_rows() {
        let rows = pascal(8);
        assert_eq!(rows.len(), 8);
        // Row 7 (0-indexed) should be [1, 7, 21, 35, 35, 21, 7, 1]
        assert_eq!(rows[7], vec![1, 7, 21, 35, 35, 21, 7, 1]);
    }

    #[test]
    fn test_row_symmetry() {
        let rows = pascal(10);
        for row in &rows {
            let reversed: Vec<u64> = row.iter().rev().copied().collect();
            assert_eq!(row, &reversed);
        }
    }

    #[test]
    fn test_next_row() {
        assert_eq!(next_row(&[1]), vec![1, 1]);
        assert_eq!(next_row(&[1, 1]), vec![1, 2, 1]);
        assert_eq!(next_row(&[1, 2, 1]), vec![1, 3, 3, 1]);
    }

    #[test]
    fn test_recursive_matches_iterative() {
        for n in 0..10 {
            assert_eq!(pascal(n), pascal_recursive(n), "Mismatch at n={}", n);
        }
    }

    #[test]
    fn test_fold_matches_iterative() {
        for n in 0..10 {
            assert_eq!(pascal(n), pascal_fold(n), "Fold mismatch at n={}", n);
        }
    }
}

Deep Comparison

OCaml vs Rust: Pascal's Triangle

Side-by-Side Code

OCaml

let next_row row =
  List.map2 (+) (0 :: row) (row @ [0])

let pascal n =
  let rec go row i =
    if i > n then []
    else row :: go (next_row row) (i + 1)
  in go [1] 1

Rust (idiomatic)

pub fn next_row(row: &[u64]) -> Vec<u64> {
    std::iter::once(&0)
        .chain(row.iter())
        .zip(row.iter().chain(std::iter::once(&0)))
        .map(|(a, b)| a + b)
        .collect()
}

pub fn pascal(n: usize) -> Vec<Vec<u64>> {
    std::iter::successors(Some(vec![1u64]), |prev| Some(next_row(prev)))
        .take(n)
        .collect()
}

Rust (functional/recursive)

pub fn pascal_recursive(n: usize) -> Vec<Vec<u64>> {
    fn go(row: Vec<u64>, i: usize, n: usize) -> Vec<Vec<u64>> {
        if i > n { return Vec::new(); }
        let next = next_row(&row);
        let mut result = vec![row];
        result.extend(go(next, i + 1, n));
        result
    }
    if n == 0 { return Vec::new(); }
    go(vec![1], 1, n)
}

Type Signatures

Concept	OCaml	Rust
Next row	`val next_row : int list -> int list`	`fn next_row(row: &[u64]) -> Vec<u64>`
Triangle	`val pascal : int -> int list list`	`fn pascal(n: usize) -> Vec<Vec<u64>>`
Zip-add	`List.map2 (+) xs ys`	`xs.zip(ys).map(\\|(a, b)\\| a + b)`
Prepend zero	`0 :: row`	`once(&0).chain(row.iter())`
Append zero	`row @ [0]`	`row.iter().chain(once(&0))`

Key Insights

**List.map2 vs zip:** OCaml's List.map2 f xs ys applies f pairwise in one call; Rust separates zipping from mapping — .zip().map() — which is more composable but requires two steps

Prepend/append symmetry: OCaml's 0 :: row (O(1) prepend) and row @ [0] (O(n) append) have different costs; Rust's once().chain() is lazy in both directions — no allocation until collect()

**successors as recursion replacement:** Rust's std::iter::successors(seed, f) generates [seed, f(seed), f(f(seed)), ...] lazily — it's the iterator equivalent of OCaml's recursive go function, but doesn't consume stack frames

**Borrowing in next_row:** Takes &[u64] (borrows the slice) and returns an owned Vec<u64> — the caller keeps the previous row while the function builds the next one. In OCaml, GC handles this automatically

Overflow risk: OCaml's int won't overflow on 64-bit (it's 63-bit signed). Rust's u64 will panic on overflow in debug mode — for very large triangles, consider u128 or a bigint library

When to Use Each Style

Use idiomatic Rust when: You want clean, readable code — successors + take is the most Rust-native way to express "generate a sequence from a recurrence relation." It's lazy, composable, and stack-safe.

Use recursive Rust when: Teaching the algorithm structure — the recursive version maps 1:1 to the OCaml code and makes the "build row, recurse" pattern explicit. Good for understanding before refactoring to iterators.

Exercises

Implement a binomial function using Pascal's triangle row as a lookup table, and verify C(n, k) == pascals_row(n)[k] for all k from 0 to n.

Use Pascal's triangle to expand (x + y)^n symbolically: return a Vec<(i64, i64, i64)> of (coefficient, x_power, y_power) terms.

Generate the Sierpinski triangle pattern by taking Pascal's triangle modulo 2: output a visual grid where odd coefficients are filled and even ones are empty — observe the fractal structure.

Open Source Repos

functional-rust

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

Rust