= Solution
The second <partial function> accepts this one's outputs. Put this method inside the invariant class in part (b):
``
def compose[V](that: PartialFn[U, V]): PartialFn[T, V] = {
val pairs: List[(T, V)] = data.flatMap {
case (x, y) => that.get(y).map(z => (x, z)).toList
}
new PartialFn[T, V](pairs)
}
``
\b[The represented mapping is $that\circ this$], since the paper explicitly applies `that` second despite the method name. A pair is emitted exactly when this mapping supplies a `y` and `that.get(y)` supplies a `z`. Hence its <domain of a partial function> is $\{x\in\operatorname{dom}(this):this(x)\in\operatorname{dom}(that)\}$ and its value there is $that(this(x))$. This is strict <composition of partial functions>: either missing stage makes the composite undefined. Repeated equal input pairs still produce the same output, preserving the representation <invariant>. With $m$ and $k$ pairs, direct association-list lookup gives $O(m(k+1)+1)$ worst-case <time complexity>, not a hidden constant-cost dictionary lookup.
Back to article page
