Use pattern matching and an optional value to distinguish absence from a present result: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.
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 })
}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 worst-case time complexity for pairs under constant-cost key equality. Articles by others on the same topic
There are currently no matching articles.