= Solution
Use <pattern matching> and an <optional value> to distinguish absence from a present result:
``
class PartialFn[T, U](val data: List[(T, U)]) {
def get(x: T): Option[U] =
data.find { case (key, _) => key == x }.map(_._2)
def remove(x: T): PartialFn[T, U] =
new PartialFn[T, U](data.filterNot { case (key, _) => key == x })
def add(x: T, y: U): PartialFn[T, U] =
new PartialFn[T, U]((x, y) ::
data.filterNot { case (key, _) => key == x })
}
``
The representation <precondition> is that equal keys always have equal associated values, with a stable equality relation on keys. This permits harmless repeated identical pairs; it excludes conflicting outputs for one input. `get` therefore returns `Some(y)` exactly when the represented <partial function> is defined at `x`. Removing filters out every occurrence of the key and leaves all other pairs unchanged. Adding first removes every old occurrence and prepends exactly the new pair, proving the <partial function> update <postcondition> even if the input contains duplicate identical pairs. The immutable <linked list> representation leaves the original mapping unchanged. Each operation has $O(m+1)$ worst-case <time complexity> for $m$ pairs under constant-cost key equality.
Back to article page
