Skip to content

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
end
  • foldl is the one primitive, a tail-recursive case over [] and [head, ..tail]. foldr is foldl over the reversed list, and reverse, length, append, concat, filter and map are folds.
  • append is foldr(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 Float lists, since el / acc on 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 with Iter.map because 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 by nomi 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 fmt writes it one inner list per line, each on one line.