Sublist
Say whether one list equals another, sits inside it, contains it, or none of these.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: sublist.nomi
//# How two lists relate: equal, one inside the other, or neither.
/// How the first list relates to the second.
pub enum Relation
Equal
Sublist
Superlist
Unequal
end
/// How `first` relates to `second`. One list is inside another when its
/// elements appear there in order and next to each other.
pub fn sublist<T>(first: List<T>, second: List<T>) -> Relation where T: Equatable
case
first == second -> .Equal
contains_run(second, first) -> .Sublist
contains_run(first, second) -> .Superlist
_ -> .Unequal
end
end
/// Whether `run` appears in `list` with its elements next to each other.
/// Every list holds the empty run, which has no window size.
fn contains_run<T>(list: List<T>, run: List<T>) -> Bool where T: Equatable
case PositiveInt.try_from(Iter.count(run))
None -> True
Some(size) -> Iter.windows(list, size) |> Iter.any_match(&(&1 == run))
end
end
// FILE: sublist_test.nomi
import sublist.{self, Relation}
test "sublist"
[
("empty lists", [], [], Relation.Equal),
("empty list within non empty list", [], [1, 2, 3], .Sublist),
("non empty list contains empty list", [1, 2, 3], [], .Superlist),
("list equals itself", [1, 2, 3], [1, 2, 3], .Equal),
("different lists", [1, 2, 3], [2, 3, 4], .Unequal),
("false start", [1, 2, 5], [0, 1, 2, 3, 1, 2, 5, 6], .Sublist),
("consecutive", [1, 1, 2], [0, 1, 1, 1, 2, 1, 2], .Sublist),
("sublist at start", [0, 1, 2], [0, 1, 2, 3, 4, 5], .Sublist),
("sublist in middle", [2, 3, 4], [0, 1, 2, 3, 4, 5], .Sublist),
("sublist at end", [3, 4, 5], [0, 1, 2, 3, 4, 5], .Sublist),
("at start of superlist", [0, 1, 2, 3, 4, 5], [0, 1, 2], .Superlist),
("in middle of superlist", [0, 1, 2, 3, 4, 5], [2, 3], .Superlist),
("at end of superlist", [0, 1, 2, 3, 4, 5], [3, 4, 5], .Superlist),
("first list missing element from second list", [1, 3], [1, 2, 3], .Unequal),
("second list missing element from first list", [1, 2, 3], [1, 3], .Unequal),
("first list missing additional digits from second list", [1, 2], [1, 22], .Unequal),
("order matters to a list", [1, 2, 3], [3, 2, 1], .Unequal),
("same digits but different numbers", [1, 0, 1], [10, 1], .Unequal),
]
|> subtests (description, first, second, expected), description
assert sublist.sublist(first, second) == expected
end
endok sublist (18 cases)
test result: ok. 18 passed, 0 failed
How it’s written
Section titled “How it’s written”- The answer is a
Relationenum of the four outcomes, not a string. sublistis generic over anyEquatableelement, though the canonical cases are allInts.- The three checks are arms of a
casewith no subject, in the order the outcomes are tested: equal first, since equal lists also contain each other. contains_runasks whether any of the longer list’sIter.windowsof the run’s length equals the run, after answering the empty run itself, since a window of size 0 does not exist. The other way is to walk the longer list with a list pattern and askList.starts_with(rest, run)at each position, which needs no lengths.- The 18 canonical cases are one
subteststable. The first row’s[]and[]take their element type from the later rows.