This page is no longer maintained — Please continue to the home page at

Set invariance and performance

No replies
Rüdiger Klaehn
Joined: 2009-06-02,
User offline. Last seen 42 years 45 weeks ago.

Hi all,

I read in a previous discussion that Set[T] is invariant so that it
can implement Function1[T,Boolean], and that this is likely to stay
this way due to compatibility issues.

I currently have a situation where I could really use covariant sets.
Currently, when I have a set of some trait B extends A, and want to
convert it into a set of trait A, I do Set.empty[A] ++ setOfB. But
that is very inefficient and ugly.

Would it be safe to say setOfB.asInstanceOf[Set[A]] instead, and could
I somehow define an implicit method to do this automatically so that I
don't have to sprinkle my code with asInstanceOf?

best regards,


besides, there are quite a few things that I think could be improved
about the current set implementation without too much work:

val large=(1 to 1000).toSet
val small=(1 to 10).toSet

large.intersect(small) is significantly slower than
small.intersect(large). Is there a reason intersect doesn't check the
size of both arguments and does the intersection in the right order?

large.union(small) is significantly faster than small.union(large). In
the extreme case large.union(empty) returns the first argument, while
empty.union(large) rebuilds the complete set from scratch!

I understand that you can not order by size in the generic case,
because the type of the returned collection depends on the type of the
first argument. But in case of union and intersection you know that
both sides are of the same type, so you could do the size check.

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland