The maximally variant safe declarations are:
trait Rel1[+X, +Y] { val pairs: List[(X, Y)] }
trait Rel2[-X, +Y] { def relatives(x: X): List[Y] }
trait Rel3[-X, -Y] { def related(x: X, y: Y): Boolean }Leaving one or both parameters invariant is also legal but admits fewer subtyping conversions. These are type variance annotations.
For
Rel1, both parameters occur only as outputs. Scala's immutable List and Tuple2 are covariant, so a list of pairs of narrower types can safely be read as pairs of broader types. Thus both may be covariant type parameters. A contravariant declaration would permit, for example, treating a Rel1[Any, Int] containing (7, 0) as a Rel1[String, Int], then reading its first component as a String. That would be unsound; the compiler rejects the negative annotation at this output position.For
Rel2, X occurs as a method argument and therefore may be a contravariant type parameter; Y is returned in an immutable list and may be a covariant type parameter. A function that accepts every Any is safe to use where only String queries are issued. The opposite direction would be unsafe: if X were covariant, the following hypothetical conversion could call a string-only implementation with an integer:val strings: Rel2[String, Int] = new Rel2[String, Int] {
def relatives(x: String): List[Int] = List(x.length)
}
// Unsafe if Rel2 were incorrectly covariant in X:
// val arbitrary: Rel2[Any, Int] = strings
// arbitrary.relatives(7)Making
Y contravariant would instead allow an integer-valued Rel2[String, Any] to be read as a string-valued Rel2[String, String], recreating the output error.For
Rel3, both generic values are consumed and only a Boolean function result is produced, so both may be contravariant type parameters. A predicate accepting all values of broad types can answer queries restricted to narrower types. Covariance in either parameter would allow passing an unsupported value to a specialized implementation. For example, treating a string-only first-argument predicate as accepting Any would permit related(7, y) even though its body might call x.length. These are applications of the variance-position rule: method inputs reverse variance, whereas immutable outputs preserve it.[ref]Scala 2.13 variance annotations specification. Variance annotations and the change of position in method parameter types
Join on equal middle components, produce the outer pair, and eliminate duplicate outputs. Using the variant declarations from part (a):
def compose1[X, Y, Z](r: Rel1[X, Y], s: Rel1[Y, Z]): Rel1[X, Z] = {
val joined = (for {
(x, y) <- r.pairs
(middle, z) <- s.pairs
if y == middle
} yield (x, z)).distinct
new Rel1[X, Z] {
val pairs: List[(X, Z)] = joined
}
}Every produced pair has a witness
y with both required input pairs, proving soundness. Conversely, any witness for a composed pair occurs in the two input lists, so the nested traversal produces that pair; .distinct retains one occurrence, proving completeness. Thus the result represents , with each pair listed once, even if either input lists duplicates or several witnesses yield the same outer pair. Equality of middle values is assumed to implement the relation's intended key equality. The nested join examines candidate pairs before duplicate elimination.For each requested
x, enumerate its middle relatives and then each middle value's relatives in the second relation:def compose2[X, Y, Z](r: Rel2[X, Y], s: Rel2[Y, Z]): Rel2[X, Z] =
new Rel2[X, Z] {
def relatives(x: X): List[Z] =
r.relatives(x).flatMap(y => s.relatives(y)).distinct
}A returned
z is present exactly when some enumerated y witnesses the two relation memberships. Conversely, every such witness appears in r.relatives(x), and its z appears in s.relatives(y), so no composed relative is omitted. .distinct removes repeated endpoints, including repetitions produced through different witnesses. This is the same composition of relations as part (b), represented one queried row at a time. Neither the entire first carrier nor the entire result must be enumerated in advance. The relation operations must remain consistent while the returned view is used; changing their underlying state would make this a live view rather than a snapshot.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, 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 and && use short-circuit evaluation; with an empty middle carrier, the answer is false. Each query uses at most 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.
Articles by others on the same topic
There are currently no matching articles.