Collections in Scala

[bearophile]

This post is mostly for Andrei. "Fighting Bit Rot with Types (Experience Report: Scala Collections)" by M. Odersky, A. Moors, found in Lambda the Ultimate blog:
http://lampwww.epfl.ch/~odersky/papers/fsttcs2009.pdf

Few quotations:

Page 431:
>For example, class List[+T] introduces the type constructor List, whose type parameter is covariant. This means that List[A] is a subtype of List[B] iff A is a subtype of B. With a contravariant type parameter, this is inverted, so that class OutputChannel[-T] entails that OutputChannel[A] is a subtype of OutputChannel[B] iff A is a supertype of B. Without an explicit variance annotation, type arguments must be equal for the constructed types to be comparable.<


Page 432:
>and c.map(f) produces a new collection with the same size as c, where each element is the result of applying f to the corresponding element of c. These operations are defined uniformly for all collections. When they return a collection result, it is usually of the same class as the collection on which the operation was applied. For instance if xs is a list then xs map (_ + 1) would yield another list, but if xs was an array, the same call would again yield an array<

So a map on an array returns an array, and a map on a list returns a list. This is nice. But there are corner cases:

scala> BitSet(1,2,3) map (_.toString+"!")
res1: scala.collection.immutable.Set[java.lang.String] = Set(1!, 2!,
3!)
Because the result type of toString is String and not Int, the result of the map cannot be
a BitSet. Instead a general Set[String] is returned.


Another two cases (page 437):

scala> Map("a" -> 1, "b" -> 2) map { case (x, y) ) (y, x) }
res2: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a, 2 -> b)

scala> Map("a" -> 1, "b" -> 2) map { case (x, y) ) y }
res3: scala.collection.immutable.Iterable[Int] = List(1, 2)

The first function swaps two arguments of a key/value pair. The result of mapping this function is again a map, but now going in the other direction. In fact, the original yields the inverse of the original map, provided it is invertible. The second function, however, maps the key/value pair to an integer, namely its value component. In that case, we cannot form a Map from the results, but we can still form an Iterable, which is the base trait of Map.


Then the paper starts talking about Implicits.
There is enough food for Andrei, the paper is nice.

Bye,
bearophile