= Solution
An <immutable object> can widen its element type when adding a value by returning a new object. Introduce a <lower type bound> $U>:T$ on the method's fresh <type parameter>.
``
class ISet[+T](contents: List[T]) {
private val elems: List[T] = contents.distinct
def add[U >: T](x: U): ISet[U] = {
val widened: List[U] = elems
if (widened.contains(x)) new ISet[U](widened)
else new ISet[U](x :: widened)
}
def delete(): (T, ISet[T]) = {
require(elems.nonEmpty)
(elems.head, new ISet[T](elems.tail))
}
}
``
As before, the <representation invariant> excludes duplicates, and the <abstraction function> returns the unordered <set> of entries. The constructor normalization makes the <representation invariant> hold even for repeated initial entries. Both operations construct a fresh <set> object and leave the original object unchanged, including when addition finds an existing member.
For a receiver representing $S$, the new object returned by `add` represents $S\cup\{x\}$. Deletion returns a pair $(x,R)$ with $x\in S$ and $R$ representing $S\setminus\{x\}$. Crucially,
$$
\boxed{add[U>:T](x:U):ISet[U],\qquad delete():(T,ISet[T]).}
$$
The widened <list> is valid because immutable `List` itself has a <covariant type parameter>. A client can view an `ISet[Int]` as `ISet[Any]`, but adding a <string> creates a separate widened result; it cannot put a <string> into the old <integer> <set>. This explains how using <immutable objects> makes the desired <type variance> sound. A direct `add(x: T)` on a covariant <software class> would still violate the <variance-position rule>; immutability alone does not repair an incorrectly typed method signature.
Back to article page
