List Ops
Implement append, concatenate, filter, length, map, both folds and reverse without the built-in list functions.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: list_ops.nomi
//# The exercise asks for these without the standard library's list and Iter
//# functions, so `foldl` walks the list with a pattern and the rest are
//# folds.
/// Folds `list` from the left: `f(f(f(initial, a), b), c)`.
pub fn foldl<T, U>(list: List<T>, initial: U, f: (U, T) -> U) -> U
case list
[] -> initial
[head, ..tail] -> foldl(tail, f(initial, head), f)
end
end
/// Folds `list` from the right: `f(f(f(initial, c), b), a)`.
pub fn foldr<T, U>(list: List<T>, initial: U, f: (U, T) -> U) -> U
foldl(reverse(list), initial, f)
end
/// The items of `list` in the opposite order.
pub fn reverse<T>(list: List<T>) -> List<T>
foldl(list, [], fn reversed, item -> [item, ..reversed])
end
/// How many items `list` holds.
pub fn length<T>(list: List<T>) -> Int
foldl(list, 0, fn count, _item -> count + 1)
end
/// The items of `first`, then the items of `second`.
pub fn append<T>(first: List<T>, second: List<T>) -> List<T>
foldr(first, second, fn rest, item -> [item, ..rest])
end
/// The items of every list in `lists`, in order, in one list.
pub fn concat<T>(lists: List<List<T>>) -> List<T>
foldr(lists, [], fn rest, list -> append(list, rest))
end
/// The items of `list` that `keep` holds for.
pub fn filter<T>(list: List<T>, keep: (T) -> Bool) -> List<T>
foldr(list, [], fn rest, item -> if keep(item) then [item, ..rest] else rest)
end
/// `f` applied to each item of `list`.
pub fn map<T, U>(list: List<T>, f: (T) -> U) -> List<U>
foldr(list, [], fn rest, item -> [f(item), ..rest])
end
// FILE: list_ops_test.nomi
import list_ops
group "append entries to a list and return the new list"
test "empty lists"
assert list_ops.append([], []) == []
end
test "list to empty list"
assert list_ops.append([], [1, 2, 3, 4]) == [1, 2, 3, 4]
end
test "empty list to list"
assert list_ops.append([1, 2, 3, 4], []) == [1, 2, 3, 4]
end
test "non-empty lists"
assert list_ops.append([1, 2], [2, 3, 4, 5]) == [1, 2, 2, 3, 4, 5]
end
end
group "concatenate a list of lists"
test "empty list"
assert list_ops.concat([] as List<List<Int>>) == []
end
test "list of lists"
assert list_ops.concat([[1, 2], [3], [], [4, 5, 6]]) == [1, 2, 3, 4, 5, 6]
end
test "list of nested lists"
lists = [
[[1], [2]],
[[3]],
[[]],
[[4, 5, 6]],
]
assert list_ops.concat(lists) == [[1], [2], [3], [], [4, 5, 6]]
end
end
group "filter list returning only values that satisfy the filter function"
test "empty list"
assert list_ops.filter([], fn x -> x % 2 == 1) == []
end
test "non-empty list"
assert list_ops.filter([1, 2, 3, 5], fn x -> x % 2 == 1) == [1, 3, 5]
end
end
group "returns the length of a list"
test "empty list"
assert list_ops.length([]) == 0
end
test "non-empty list"
assert list_ops.length([1, 2, 3, 4]) == 4
end
end
group "return a list of elements whose values equal the list value transformed by the mapping function"
test "empty list"
assert list_ops.map([], &(&1 + 1)) == []
end
test "non-empty list"
assert list_ops.map([1, 3, 5, 7], &(&1 + 1)) == [2, 4, 6, 8]
end
end
group "folds (reduces) the given list from the left with a function"
test "empty list"
assert list_ops.foldl([], 2, fn acc, el -> el * acc) == 2
end
test "direction independent function applied to non-empty list"
assert list_ops.foldl([1, 2, 3, 4], 5, fn acc, el -> el + acc) == 15
end
test "direction dependent function applied to non-empty list"
assert list_ops.foldl([1.0, 2.0, 3.0, 4.0], 24.0, fn acc, el -> el / acc) == 64.0
end
end
group "folds (reduces) the given list from the right with a function"
test "empty list"
assert list_ops.foldr([], 2, fn acc, el -> el * acc) == 2
end
test "direction independent function applied to non-empty list"
assert list_ops.foldr([1, 2, 3, 4], 5, fn acc, el -> el + acc) == 15
end
test "direction dependent function applied to non-empty list"
assert list_ops.foldr([1.0, 2.0, 3.0, 4.0], 24.0, fn acc, el -> el / acc) == 9.0
end
end
group "reverse the elements of the list"
test "empty list"
assert list_ops.reverse([]) == []
end
test "non-empty even-length list"
assert list_ops.reverse([1, 3, 5, 7]) == [7, 5, 3, 1]
end
test "non-empty odd-length list"
assert list_ops.reverse([1, 3, 5, 7, 9, 11, 13]) == [13, 11, 9, 7, 5, 3, 1]
end
test "list of lists is not flattened"
assert list_ops.reverse([[1, 2], [3], [], [4, 5, 6]]) == [[4, 5, 6], [], [3], [1, 2]]
end
endok append entries to a list and return the new list / empty lists
ok append entries to a list and return the new list / list to empty list
ok append entries to a list and return the new list / empty list to list
ok append entries to a list and return the new list / non-empty lists
ok concatenate a list of lists / empty list
ok concatenate a list of lists / list of lists
ok concatenate a list of lists / list of nested lists
ok filter list returning only values that satisfy the filter function / empty list
ok filter list returning only values that satisfy the filter function / non-empty list
ok returns the length of a list / empty list
ok returns the length of a list / non-empty list
ok return a list of elements whose values equal the list value transformed by the mapping function / empty list
ok return a list of elements whose values equal the list value transformed by the mapping function / non-empty list
ok folds (reduces) the given list from the left with a function / empty list
ok folds (reduces) the given list from the left with a function / direction independent function applied to non-empty list
ok folds (reduces) the given list from the left with a function / direction dependent function applied to non-empty list
ok folds (reduces) the given list from the right with a function / empty list
ok folds (reduces) the given list from the right with a function / direction independent function applied to non-empty list
ok folds (reduces) the given list from the right with a function / direction dependent function applied to non-empty list
ok reverse the elements of the list / empty list
ok reverse the elements of the list / non-empty even-length list
ok reverse the elements of the list / non-empty odd-length list
ok reverse the elements of the list / list of lists is not flattened
test result: ok. 23 passed, 0 failed
How it’s written
Section titled “How it’s written”foldlis the one primitive, a tail-recursivecaseover[]and[head, ..tail].foldrisfoldlover the reversed list, andreverse,length,append,concat,filterandmapare folds.appendisfoldr(first, second, fn rest, item -> [item, ..rest]): the first list folded onto the second.- Both folds call
f(accumulator, item), the argument order the canonical data’s reimplemented cases fix. - The direction-dependent fold cases use
Floatlists, sinceel / accon the canonical numbers is fractional and Nomi has one/per type. - The functions are file-level and called
list_ops.map(...); the names do not clash withIter.mapbecause file qualification keeps them apart. - The file comment is
//#, the file-comment form style §49 gives for every file: a plain//comment above the first declaration is joined to it bynomi fmt. concat([])needs a typed empty list, which the test writes in place as[] as List<List<Int>>;append([], [])and the other empty cases need nothing.- The “list of nested lists” input is one literal. It is three lists deep, so
nomi fmtwrites it one inner list per line, each on one line.