Conversion from Seq to Set and back to Seq

Question

Intuitively the following should work:

case class I(i: Int)
val s = Seq(I(1),I(2),I(3))
s.sortBy(_.i)             // works
s.toSeq.sortBy(_.i)       // works
s.toSet.toSeq.sortBy(_.i) // doesn´t work

Why doesn´t it behave as expected?

Answer 1

This is a complicated impact of mixing covariant and invariant collections. Set is invariant: Set[A]. But Seq is covariant: Seq[+A]. Now, imagine you want to have a toSet method in your Seq. You might try toSet: Set[A]. But this isn't going to work, because if A is a subclass of B, then Seq[A] should be considered as a subclass of Seq[B]. However, Seq[A] insists on returning a Set[A] which is not a subclass of Seq[B]. So our typing is broken.

If, on the other hand, we specify toSeq[B >: A]: Set[B] then everything is fine: if we promise we can return any superclass, then Seq[A] can return Set[B] as well as Set[C] where C is a superclass of B. Seq[B] promised to return Set[B] or some Set[C] also, so we're in the clear: the method on Seq[A] can do everything that the method on Seq[B] can do.

But now look at what the poor typer is faced with:

s.toSet[B >: I]
 .toSeq/* Type B >: I*/
 .sortBy[C](/* some f:B => C */)(/* implicit ordering on C */)

There is a way to resolve this--namely to decide that B is I and type the function and C accordingly. But it gets to be a pretty complicated search, and it's more than the compiler can handle right now. So it asks you to help it out with the input type to the function so it knows B at that point (and then can propagate it back to toSet).

But you can, if you want, help it out at a number of levels:

s.toSet[I].toSeq.sortBy(_.i)
s.toSet.toSeq.sortBy[Int](_.i)

or you can help it out by demonstrating to it that it need not consider later types when picking the best match with earlier types:

{ val temp = s.toSet; temp }.toSeq.sortBy(_.i)
s.toSet match { case x => x.toSeq.sortBy(_.i) }