Skip to content

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
end
  • The answer is a Relation enum of the four outcomes, not a string.
  • sublist is generic over any Equatable element, though the canonical cases are all Ints.
  • The three checks are arms of a case with no subject, in the order the outcomes are tested: equal first, since equal lists also contain each other.
  • contains_run asks whether any of the longer list’s Iter.windows of 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 ask List.starts_with(rest, run) at each position, which needs no lengths.
  • The 18 canonical cases are one subtests table. The first row’s [] and [] take their element type from the later rows.