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
endok flatten (11 cases)
test result: ok. 11 passed, 0 failed
How it’s written
Section titled “How it’s written”- The input is a recursive enum,
Nested: aValue Int, anArray List<Nested>, orNull. The canonical arrays mix numbers, arrays and nulls, and the enum names each kind, soflattenhandles exactly those three and the compiler checks it does. flattenisIter.flat_mapover the top level withvalues, 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
Nestedvalues in the tests,[.Value(1), .Array([.Value(2)]), .Null]. std::json’sJsoncould hold them, but it also holds strings, floats and objects, which this input never has, and there is noJsontyped 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
subteststable named by the description column. The four cases that newer ones reimplement (the same arrays, described as lists instead of arrays) are left out.