Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 8 / c / Solution

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.