Skip to content

Flatten Array

Flatten an arbitrarily nested array of integers into one flat list, leaving out nulls.

Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.

// FILE: flatten_array.nomi
//# Flattens a nested array into one list of its values, dropping nulls.

/// One element of a nested array: a value, an array of elements, or null.
pub enum Nested
    Value Int
    Array List<Nested>
    Null
end

/// Every value in `array`, at any depth, in order; nulls are left out.
pub fn flatten(array: List<Nested>) -> List<Int>
    array
    |> Iter.flat_map(values)
    |> Iter.to_list()
end

/// The values one element holds.
fn values(element: Nested) -> List<Int>
    case element
        .Value(n)        -> [n]
        .Array(elements) -> flatten(elements)
        .Null            -> []
    end
end

// FILE: flatten_array_test.nomi
import flatten_array.{self, Nested}

test "flatten"
    [
        ("empty",      [],                                      []),
        ("no nesting", [Nested.Value(0), .Value(1), .Value(2)], [0, 1, 2]),
        ("flattens a nested array", [
            .Array([.Array([])]),
        ], []),
        (
            "flattens array with just integers present",
            [
                .Value(1),
                .Array([.Value(2), .Value(3), .Value(4), .Value(5), .Value(6), .Value(7)]),
                .Value(8),
            ],
            [1, 2, 3, 4, 5, 6, 7, 8],
        ),
        ("5 level nesting", [
            .Value(0),
            .Value(2),
            .Array([
                .Array([.Value(2), .Value(3)]),
                .Value(8),
                .Value(100),
                .Value(4),
                .Array([
                    .Array([.Array([.Value(50)])]),
                ]),
            ]),
            .Value(-2),
        ], [0, 2, 2, 3, 8, 100, 4, 50, -2]),
        ("6 level nesting", [
            .Value(1),
            .Array([
                .Value(2),
                .Array([.Array([.Value(3)])]),
                .Array([
                    .Value(4),
                    .Array([.Array([.Value(5)])]),
                ]),
                .Value(6),
                .Value(7),
            ]),
            .Value(8),
        ], [1, 2, 3, 4, 5, 6, 7, 8]),
        ("null values are omitted from the final result", [.Value(1), .Value(2), .Null], [1, 2]),
        (
            "consecutive null values at the front of the array are omitted from the final result",
            [.Null, .Null, .Value(3)],
            [3],
        ),
        (
            "consecutive null values in the middle of the array are omitted from the final result",
            [.Value(1), .Null, .Null, .Value(4)],
            [1, 4],
        ),
        ("6 level nested array with null values", [
            .Value(0),
            .Value(2),
            .Array([
                .Array([.Value(2), .Value(3)]),
                .Value(8),
                .Array([.Array([.Value(100)])]),
                .Null,
                .Array([.Array([.Null])]),
            ]),
            .Value(-2),
        ], [0, 2, 2, 3, 8, 100, -2]),
        ("all values in nested array are null", [
            .Null,
            .Array([
                .Array([.Array([.Null])]),
            ]),
            .Null,
            .Null,
            .Array([.Array([.Null, .Null]), .Null]),
            .Null,
        ], []),
    ]
    |> subtests (description, array, expected), description
        assert flatten_array.flatten(array) == expected
    end
end
  • The input is a recursive enum, Nested: a Value Int, an Array List<Nested>, or Null. The canonical arrays mix numbers, arrays and nulls, and the enum names each kind, so flatten handles exactly those three and the compiler checks it does.
  • flatten is Iter.flat_map over the top level with values, which returns one element’s values: [n] for a value, the flattened array for an array, and [] for a null. The recursion is between the two functions, one call per nested array.
  • The canonical arrays are written as Nested values in the tests, [.Value(1), .Array([.Value(2)]), .Null]. std::json’s Json could hold them, but it also holds strings, floats and objects, which this input never has, and there is no Json typed literal to write them as JSON.
  • The table needs no annotation. Its first row’s arrays are empty, the second row names the enum, Nested.Value(0), and every variant after it is bare.
  • The 11 current canonical cases are one subtests table named by the description column. The four cases that newer ones reimplement (the same arrays, described as lists instead of arrays) are left out.