Skip to content

Pascal's Triangle

Build the first rows of Pascal’s triangle, where each value is the sum of the two above it.

Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.

// FILE: pascals_triangle.nomi
//# The first rows of Pascal's triangle.

/// The first `count` rows of Pascal's triangle, starting from `[1]`.
pub fn rows(count: Int) -> List<List<Int>>
    Iter.iterate([1], next_row)
    |> Iter.take(count)
    |> Iter.to_list()
end

/// The row below `row`: each value is the sum of the two above it, with a
/// zero standing in past either end.
fn next_row(row: List<Int>) -> List<Int>
    Iter.zip([0, ..row], [..row, 0])
    |> Iter.map(fn (left, right) -> left + right)
    |> Iter.to_list()
end

// FILE: pascals_triangle_test.nomi
import pascals_triangle

test "rows"
    [
        ("zero rows",  0, []),
        ("single row", 1, [[1]]),
        ("two rows",   2, [[1], [1, 1]]),
        ("three rows", 3, [[1], [1, 1], [1, 2, 1]]),
        ("four rows",  4, [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]),
        ("five rows",  5, [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]),
        (
            "six rows",
            6,
            [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]],
        ),
        (
            "ten rows",
            10,
            [
                [1],
                [1, 1],
                [1, 2, 1],
                [1, 3, 3, 1],
                [1, 4, 6, 4, 1],
                [1, 5, 10, 10, 5, 1],
                [1, 6, 15, 20, 15, 6, 1],
                [1, 7, 21, 35, 35, 21, 7, 1],
                [1, 8, 28, 56, 70, 56, 28, 8, 1],
                [1, 9, 36, 84, 126, 126, 84, 36, 9, 1],
            ],
        ),
    ]
    |> subtests (description, count, expected), description
        assert pascals_triangle.rows(count) == expected
    end
end
  • rows is Iter.iterate([1], next_row) under Iter.take(count): the triangle is an unbounded sequence of rows, each from the last, and the count only says how many to keep.
  • next_row zips the row shifted right by a leading zero ([0, ..row]) with the row followed by a zero ([..row, 0]) and adds the pairs.
  • The eight canonical cases are one subtests table.