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?

Solution

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) }

Comments

[Peter Schmitz]

Yes, I know how to overcome the problem, but why does it persist in my case? It isn´t intuitively.

[Peter Schmitz]

Rex, thanks for that enlightenment, that´s what I wanted. Such answers not only solves the problem, it also gives me a deeper understanding what´s happening. Thank you very much! What a pity, one can only upvote once :D