= Solution
Use the first <binary relation> for the outer generator, the second for the inner generator, and match their middle values. Different witnesses can generate the same output pair, so apply <duplicate removal>:
``
relcomp :: Eq a => [(a, a)] -> [(a, a)] -> [(a, a)]
relcomp r s = removedup [(a, b) | (a, c) <- r,
(d, b) <- s, c == d]
``
The guards give precisely the existential witness required for <composition of relations>:
$$
\boxed{(a,b)\in\operatorname{relcomp}(R,S)\iff\exists c:\ (a,c)\in R\ \land\ (c,b)\in S.}
$$
Every output is sound by its generating witness, and every witness is visited for finite inputs. <Duplicate removal> converts the resulting enumeration back to the required representation by distinct pairs.
Back to article page
