Collections in Scala

Final lecture of the second day is again by Martin Odersky on Scala. Before he moves he mentions that the example of the previous lecture can be done in Scala in about 20 lines, while best shortest Java solution (by Josh Broch) is already 100 lines and it is not very beautiful. I will try to find this example on post it here, so you can enjoy it too.  Found it (in slides of Martin of a talk at Sioux, which is funny, since during the break I was talking to someone from Sioux who mentioned exactly this talk.


In Scala there are parallel collection, the work is then divided over processors. Each thread gets a work queue which is split exponentially (larger work items are placed at the end of the queue). When a tread is ready, it will start to steal work items from the end of the queue, so chances are low that threads take the same item. When threads get closer to the end, they start to take smaller chunks, to prevent that all threads will be waiting for this thread.

“Now comes: the dark side”

How is this all implemented? Everything is a library, there is no hidden magic behind the curtain of Scala collections. One of the hard problems was that bulk operations (like map) need to return the the same type as their left operand (this is different from other languages, like C# Erik Meijer points out that this is not true for C#, where you always get same type) This choice is important to be able to support parallelism nicely, since this returning type might not be optimized for parallelism.

This choice did result in the fact that there was a lot of duplication of methods, for the different collection types, and soon inconsistencies started to occur. All these (in Lists.Scala) are now depreciated and Martin tried to do it better in a new version, by abstracting out the type constructor.

This would look something like this:


(Martin’s exact slide, but taken from the same Sioux slides)

To get this to work, all sets need to implement a builder, but this was not enough to solve this problem, for details, have a look at the subsequent slides in the above mentioned Sioux talk, since at this point, Martin’s talk ended because of time constraints. Great intro into Scala though!