Skip to content

Strain

Implement keep and discard, which split a collection by a predicate, without the standard library’s filter.

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

// FILE: strain.nomi
//# The exercise asks for `keep` and `discard` without the standard
//# library's filter, so `keep` walks the list with a pattern.

/// The items of `list` that `predicate` holds for, in order.
pub fn keep<T>(list: List<T>, predicate: (T) -> Bool) -> List<T>
    case list
        []                                  -> []
        [head, ..tail] when predicate(head) -> [head, ..keep(tail, predicate)]
        [_head, ..tail]                     -> keep(tail, predicate)
    end
end

/// The items of `list` that `predicate` does not hold for, in order.
pub fn discard<T>(list: List<T>, predicate: (T) -> Bool) -> List<T>
    keep(list, &(not predicate(&1)))
end

// FILE: strain_test.nomi
import strain

test "keep integers"
    cases: List<(String, List<Int>, (Int) -> Bool, List<Int>)> = [
        ("keep on empty list returns empty list", [],        fn _x -> True,  []),
        ("keeps everything",                      [1, 3, 5], fn _x -> True,  [1, 3, 5]),
        ("keeps nothing",                         [1, 3, 5], fn _x -> False, []),
        ("keeps first and last",                  [1, 2, 3], &(&1 % 2 == 1), [1, 3]),
        ("keeps neither first nor last",          [1, 2, 3], &(&1 % 2 == 0), [2]),
    ]

    subtests cases, (description, list, predicate, expected), description
        assert strain.keep(list, predicate) == expected
    end
end

test "keeps strings"
    words = ["apple", "zebra", "banana", "zombies", "cherimoya", "zealot"]

    assert strain.keep(words, &String.starts_with(&1, "z")) == ["zebra", "zombies", "zealot"]
end

test "keeps lists"
    lists = [[1, 2, 3], [5, 5, 5], [5, 1, 2], [2, 1, 2], [1, 5, 2], [2, 2, 1], [1, 2, 5]]

    assert strain.keep(lists, &(5 in &1)) == [
        [5, 5, 5],
        [5, 1, 2],
        [1, 5, 2],
        [1, 2, 5],
    ]
end

test "discard integers"
    cases: List<(String, List<Int>, (Int) -> Bool, List<Int>)> = [
        ("discard on empty list returns empty list", [],        fn _x -> True,  []),
        ("discards everything",                      [1, 3, 5], fn _x -> True,  []),
        ("discards nothing",                         [1, 3, 5], fn _x -> False, [1, 3, 5]),
        ("discards first and last",                  [1, 2, 3], &(&1 % 2 == 1), [2]),
        ("discards neither first nor last",          [1, 2, 3], &(&1 % 2 == 0), [1, 3]),
    ]

    subtests cases, (description, list, predicate, expected), description
        assert strain.discard(list, predicate) == expected
    end
end

test "discards strings"
    words = ["apple", "zebra", "banana", "zombies", "cherimoya", "zealot"]

    assert strain.discard(words, &String.starts_with(&1, "z")) == ["apple", "banana", "cherimoya"]
end

test "discards lists"
    lists = [[1, 2, 3], [5, 5, 5], [5, 1, 2], [2, 1, 2], [1, 5, 2], [2, 2, 1], [1, 2, 5]]

    assert strain.discard(lists, &(5 in &1)) == [[1, 2, 3], [2, 1, 2], [2, 2, 1]]
end
  • keep is a case over [] and [head, ..tail], with a when guard on the arm that keeps the head. Each kept item is consed onto what the rest keeps, so the order is the input’s with no reverse.
  • discard is keep with the predicate negated, &(not predicate(&1)), so the walk is written once.
  • Both are generic over the item type, which the canonical data asks for with integers, strings and lists of integers. The integer cases are two subtests tables, one per function, whose predicate column is a function value, (Int) -> Bool; the string and list cases are one test each, since a table’s columns have one type.
  • The canonical predicates are written as captures (&(&1 % 2 == 1), &String.starts_with(&1, "z"), &(5 in &1)), and the constant ones as fn _x -> True.