= Solution
A `Rel3` provides only a membership test for a supplied pair. It gives no way to enumerate the finite middle carrier `Y`, enumerate one element's relatives, or even obtain a first value of type `Y`. Finiteness alone supplies no generic enumeration operation. To answer the existential query for the composed relation, \b[supply a complete finite enumeration of the middle carrier explicitly]:
``
def compose3[X, Y, Z](r: Rel3[X, Y], s: Rel3[Y, Z],
middleValues: List[Y]): Rel3[X, Z] = {
val witnesses = middleValues.distinct
new Rel3[X, Z] {
def related(x: X, z: Z): Boolean =
witnesses.exists(y => r.related(x, y) && s.related(y, z))
}
}
``
The <precondition> is that `middleValues` contains every admissible middle value, or at least every possible witness. Extra irrelevant values do not change the answer if the two membership tests are defined for them. The <postcondition> is precisely $\exists y\in Y:\ R(x,y)\land S(y,z)$. `.exists` and `&&` use <short-circuit evaluation>; with an empty middle carrier, the answer is false. Each query uses at most $|Y|$ pairs of membership tests, apart from the one-time duplicate elimination.
An alternative interface can expose `def rightDomain: List[Y]` together with the first predicate, with an explicit completeness contract. Such an output position is incompatible with retaining a contravariant `Y` in that extended trait, so its variance must be reconsidered. Passing the enumeration separately leaves the safe base `Rel3[-X,-Y]` unchanged.
The information gap is substantive. A black-box algorithm making finitely many membership queries cannot rule out a witness at an unexamined middle value: two relations can agree on every inspected pair while differing only by a fresh witness that makes the composition true. A finite but unenumerated carrier can be enlarged to include that witness. A complete explicit enumeration, a known traversable carrier, or an equivalent relatives-enumeration interface removes this obstruction. This is <finite-domain composition from relation predicates>, rather than a problem solvable merely by nesting the two Boolean-valued methods.
Back to article page
