Use the representation invariant that each input occurs at most once in
data. It is an immutable finite partial function, so extending or removing an input returns a new object. The source comment get(x) returns Some(x) contradicts both the type signature Option[U] and the input-output semantics: it must return Some(y) when .class PartialFn[T,U](val data: List[(T,U)]) {
require(data.map(_._1).distinct.size == data.size)
def get(x: T): Option[U] =
data.find(p => p._1 == x).map(_._2)
def add(x: T, y: U): PartialFn[T,U] =
new PartialFn[T,U]((x,y) :: data.filterNot(p => p._1 == x))
def remove(x: T): PartialFn[T,U] =
new PartialFn[T,U](data.filterNot(p => p._1 == x))
def compose[V](that: PartialFn[U,V]): PartialFn[T,V] = {
val pairs: List[(T,V)] = data.flatMap { case (x,y) =>
that.get(y).toList.map(z => (x,z))
}
new PartialFn[T,V](pairs)
}
}get returns an optional value rather than inventing a result outside the domain of a function. add removes any old pair for its input before inserting the replacement; remove retains exactly the other pairs. In compose, undefined intermediate outputs contribute an empty list; defined outputs contribute one pair. Hence uniqueness of input keys is preserved.The printed composition order is deliberately followed:This is the stated function composition, even though some libraries use the name
compose for the opposite order.A covariant type parameter may be produced but not consumed directly. Widen the output type of
add through a lower type bound. In compose, the first parameter of CoPartialFn is invariant, so replace its occurrence of U by a fresh type parameter W with lower type bound U.class CoPartialFn[T,+U](val data: List[(T,U)]) {
require(data.map(_._1).distinct.size == data.size)
def get(x: T): Option[U] =
data.find(p => p._1 == x).map(_._2)
def add[V >: U](x: T, y: V): CoPartialFn[T,V] = {
val old: List[(T,V)] = data.filterNot(p => p._1 == x)
new CoPartialFn[T,V]((x,y) :: old)
}
def remove(x: T): CoPartialFn[T,U] =
new CoPartialFn[T,U](data.filterNot(p => p._1 == x))
def compose[V, W >: U](that: CoPartialFn[W,V]): CoPartialFn[T,V] = {
val pairs: List[(T,V)] = data.flatMap { case (x,y) =>
that.get(y).toList.map(z => (x,z))
}
new CoPartialFn[T,V](pairs)
}
}List, Tuple2, and Option are covariant in their element/output parameters, so data, get, and remove are valid producers. The variance-position rule permits U in the lower type bounds; every value of U can be passed to that.get, since . No cast or mutation through a widened reference is needed.[ref]Scala 2.11 basic declarations and definitions specification. Variance Annotations: variance positions and lower-bound widening
The input-key representation invariant and the partial function semantics are unchanged.Because The lower type bound gives , so stored output values can be widened into
Set is invariant in the specified Scala library, even returning Set[U] would place the class's covariant type parameter in an invariant position. Introduce a fresh widened type for each lifting.class CoPartialFnExt[T,+U](data: List[(T,U)])
extends CoPartialFn[T,U](data) {
def forwardLift[V >: U](s: Set[T]): Set[V] = {
val ys: List[V] = this.data.collect {
case (x,y) if s.contains(x) => y
}
ys.toSet
}
def backwardLift[V >: U](s: Set[V]): Set[T] =
this.data.collect {
case (x,y) if s.contains(y) => x
}.toSet
}List[V] or passed to s.contains. Both exposed Set types use invariant method type parameters, not the class's U. Calling forwardLift[U] or backwardLift[U] when the concrete output type is known recovers the exact output universe; a broader admissible universe is also safe.For a partial function, the forward formula is understood only for inputs in its domain of a function. The implementations therefore computeThe conversion to a set removes repeated images. Inputs not in the domain of a function contribute nothing to either lifting.
Articles by others on the same topic
There are currently no matching articles.