Scala 2.8 Arrays are not Traversables

One performance/consistency change that has been make in Scala 2.8 is to make Scala Array always be a Java Array. This has some consequences which we will examine in this post. The biggest one is that Array is not a Scala Collection/Traversable. It is implicitly converted to one but it is not an instance of a Traversable. There are several reasons this was done. Probably the biggest is for performance. Because a Scala array is a Java array there is no overhead when using a Scala array.

Thanks to implicit type conversion all the normal collection methods are useable with an array. Even better, after running a method like map the result will again be a Java array. So the API is much more consistent.

An example illustrating that an Array is not a Traversable:

1. // This does not compile (which is good) 
2. // because Traversable[Int] can never be an array
3. scala> def x(t:Traversable[Int]) = t match {
4.      | case x : Array[Int] => true          
5.      | }
6. < console>:13: error: pattern type is incompatible with expected type;
7.  found   : Array[Int]
8.  required: Traversable[Int]
9.        case x : Array[Int] => true
10.                 ^
11. < console>:13: error: type mismatch;
12.  found   : Array[Int]
13.  required: Traversable[Int]
14.        case x : Array[Int] => true
15.               ^

Another example:

1. scala> def x(t:Traversable[Int]) = t.isInstanceOf[Array[_]]
2. x: (t: Traversable[Int])Boolean
4. /* this evaluates to false because Array is converted
5.  * to WrappedArray because it has to be implicitly converted
6.  * to a Traversable.  Since Array is not a Traversable the resulting 
7.  * object is not an Array
8.  */
9. scala> x(Array(1,2,3))                                     
10. res24: Boolean = false
12. scala> def x(t:Traversable[Int]) = println(t)
13. x: (t: Traversable[Int])Unit
15. // This method call demonstrates the previous assertion
16. scala> x(Array(1,2,3))                                            
17. WrappedArray(1, 2, 3)

So suppose you want to be able to accept and use arrays and Traversables in a method but you want to be able to
check that the parameter is an Array. Why not match against WrappedArray. You probably can, but you may get performance improvements in some cases if you don't require wrapping the array.

For a more concrete example of why you may want to do this. In a Input/Output routine I wrote I would write the data one way if the input was an Array: stream.write(array). But if the input was a traversable then I would have to handle it differently. My particular issue was more complicated than that but that is the basic issue.

So the work around is to define a Generic parameter for the method:

1. scala> def x[T <% Traversable[Int]](t:T) = t match { 
2.      | case x : Array[Int] => true                                
3.      | }
4. x: [T](t: T)(implicit evidence$1: (T) => Traversable[Int])Boolean
6. scala> x(Array(1,2,3))                               
7. res27: Boolean = true

A quick note. ScalaDays Rocks! Wish you were here :)

This topic just demonstrates a cute little trick that can occasionally be quite useful:

1. scala> List(1,2,3) ++ Some(4)
2. res0: List[Int] = List(1, 2, 3, 4)
4. scala> List(1,2,3) ++ None   
5. res1: List[Int] = List(1, 2, 3)

Options are implicitly converted to Iterables, so Options can be appended to collections.

1. scala> val x : Iterable[Int] = None       
2. x: Iterable[Int] = List()
4. scala> val x : Iterable[Int] = Some(4)
5. x: Iterable[Int] = List(4)

Creating Custom Traversable implementations

One of the most talked about features of Scala 2.8 is the improved Collections libraries. Creating your own implementation is trivial, however if you want your new collection to behave the same way as all the included libraries there are a few tips you need to be aware of.

Note: All of these examples can either be ran in the REPL or put in a file and ran

Starting with the simple implementation:

1. import scala.collection._
2. import scala.collection.generic._
4. class MyColl[A](seq : A*) extends Traversable[A] {
5.     // only abstract method in traversable is foreach... easy :) 
6.   def foreach[U](f: A => U) = util.Random.shuffle(seq.toSeq).foreach(f)
7. }

This is a silly collection I admit but it is custom :).

This example works but if you test the result of a map operation (or any other operation that returns a new instance of the collection) you will notice it is not an instance of MyColl. This is expected because unless otherwise defined Traversable will return a new instance of Traversable.

To demonstrate run the following tests:

1. val c = new MyColl(1, 2, 3)
2. println (c mkString ",")
3. println(c mkString ",")
5. println(c drop 1 mkString ",")
7. // this two next assertions fail (see following explanation)
8. assert(c.drop(1).isInstanceOf[MyColl[_]])
9. assert((c map {_ + 1}).isInstanceOf[MyColl[_]])

Both assertions will fail. The reason for these failures is because the collection is immutable which dictates by necessity that a new object must be returned from filter/map/etc... Since the Traversable trait returns instances of Traversable these two assertions fail. The easiest way to make these methods return an instance of MyColl is to make the following changes/additions.

1. import scala.collection._
2. import scala.collection.generic._
4. /*
5. Adding GenericTraversableTemplate will delegate the creation of new
6. collections to the companion object.  Adding the trait and
7. companion object causes all the new collections to be instances of MyColl
8. */
9. class MyColl[A](seq : A*) extends Traversable[A] 
10.                              with GenericTraversableTemplate[A, MyColl] {
11.   override def companion = MyColl
12.   def foreach[U](f: A => U) = util.Random.shuffle(seq.toSeq).foreach(f)
13. }
15. // The TraversableFactory trait is required by GenericTraversableTemplate
16. object MyColl extends TraversableFactory[MyColl] {
17. /* 
18. If you look at the signatures of many methods in TraversableLike they have an
19. implicit parameter canBuildFrom.  This allows one to define how the returned collections
20. are built.  For example one could make a list's map method return a Set
21. In this case we define the default canBuildFrom for MyColl
22. */
23.   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyColl[A]] = new GenericCanBuildFrom[A]
24. /*  
25. The method that builds the new collection.  This is a simple implementation
26. but it works.  There are other implementations to assist with implementation if
27. needed
28. */
29.   def newBuilder[A] = new scala.collection.mutable.LazyBuilder[A,MyColl[A]] {
30.     def result = {
31.       val data = parts.foldLeft(List[A]()){(l,n) => l ++ n}
32.       new MyColl(data:_*)
33.     }
34.   }
35. }

Now instances of MyColl will be created by the various filter/map/etc... methods and that is fine as long as the new object is not required at compile-time. But suppose we added a method to the class and want that accessible after applying methods like map and filter.

Adding val o : MyColl[Long] = c map {_.toLong} to the assertions will cause a compilation error since statically the class returned is Traversable[Long]. The fix is easy.

All that needs to be done is to add with TraversableLike[A, MyColl[A]] to MyColl and we are golden. There may be other methods as well but this works and is simple.

Note that the order in which the traits are mixed in is important. TraversableLike[A, MyColl[A]] must be mixed in after Traversable[A]. The reason is that we want methods like map and drop to return instances of MyColl (statically as well as dynamically). If the order was reversed then those methods would return Traversable event though statically the actual instances would still be MyColl.

1. import scala.collection._
2. import scala.collection.generic._
4. class MyColl[A](seq : A*) extends Traversable[A]
5.                              with GenericTraversableTemplate[A, MyColl] 
6.                              with TraversableLike[A, MyColl[A]] {
7.   override def companion = MyColl
8.   def foreach[U](f: A => U) = util.Random.shuffle(seq.toSeq).foreach(f)
9. }
11. object MyColl extends TraversableFactory[MyColl] {  
12.   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyColl[A]] = new GenericCanBuildFrom[A]
13.   def newBuilder[A] = new scala.collection.mutable.LazyBuilder[A,MyColl[A]] {
14.     def result = {
15.       val data = parts.foldLeft(List[A]()){(l,n) => l ++ n}
16.       new MyColl(data:_*)
17.     }
18.   }
19. }

Now add in a new method to demonstrate that the new collection works as desired and we are done.

The following is the complete implementation with the tests. You can put it in a file and run scala <filename> or paste it into a REPL

1. import scala.collection._
2. import scala.collection.generic._
3. import scala.collection.mutable.{ Builder, ListBuffer }
5. class MyColl[A](seq : A*) extends Traversable[A]
6.                              with GenericTraversableTemplate[A, MyColl] 
7.                              with TraversableLike[A, MyColl[A]] {
8.   override def companion = MyColl
9.   def foreach[U](f: A => U) = util.Random.shuffle(seq.toSeq).foreach(f)
11.   def sayhi = println("hi!")
12. }
14. object MyColl extends TraversableFactory[MyColl] {  
15.   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyColl[A]] = new GenericCanBuildFrom[A]
16.   def newBuilder[A] = new ListBuffer[A] mapResult (x => new MyColl(x:_*))
17. }
19. val c = new MyColl(1, 2, 3)
20. println (c mkString ",")
21. println(c mkString ",")
23. assert(c.drop(1).isInstanceOf[MyColl[_]])
24. assert((c map {_ + 1}).isInstanceOf[MyColl[_]])
26. val o : MyColl[Int] = c filter {_ < 2}
27. println(o mkString "," )
28. o.sayhi

Elidable (remove method calls at compile time)

In Scala 2.8 there is a useful annotation called 'elidable'. This annotation flags a method so that given certain compiler flags all calls to the method will be removed. This is handy if you are writing a logger. The log methods can be annotated so that when compiling for production all log calls below a certain level would be removed from the compiled code. Several of the methods in Predef are annotated with elidable. Specifically, assume, assert and require.

The elidable annotation takes an Int parameter which specifies the priority of the method. The lower the integer the more likely the method would be removed during compilation. The elidable object defines several values that are used in our example.

When compiling with the -Xelide-below , the compiler parameter will remove all calls to elidable methods value and below.

To try the following example copy the example into a scala file (elidable.scala for example) and compile as indicated below:

1. package example
3. import scala.annotation.elidable
4. import scala.annotation.elidable._
6. object ElidableExamples {
7.     @elidable(ALL) def all = println("all")
8.     @elidable(ASSERTION) def assertion = println("assertion")
9.     @elidable(CONFIG) def config = println("config")
10.     @elidable(FINE) def fine = println("fine")
11.     @elidable(FINER) def finer = println("finer")
12.     @elidable(FINEST) def finest = println("finest")
13.     @elidable(INFO) def info = println("info")
14.     @elidable(OFF) def off = println("off")
15.     @elidable(SEVERE) def severe = println("severe")
16.     @elidable(WARNING) def warning = println("warning")
17. }
19. object Main extends Application {
20. println("starting")
21. import ElidableExamples._
22. all
23. assertion
24. config
25. fine
26. finer
27. finest
28. info
29. off
30. severe
31. warning
32. println("ending")
34. assert(false, "boom!")
35. }

Output from scalac elidable.scala && scala example.Main

starting
assertion
off
ending
java.lang.AssertionError: assertion failed: boom!
at scala.Predef$.assert(Predef.scala:93)
at example.Main$.(elidable.scala:34)
at example.Main$.(elidable.scala)
at example.Main.main(elidable.scala)

Output from scalac -Xelide-below 0 elidable.scala && scala example.Main

starting
assertion
config
fine
finer
finest
info
off
severe
warning
ending
java.lang.AssertionError: assertion failed: boom!
at scala.Predef$.assert(Predef.scala:93)
at example.Main$.(elidable.scala:34)
at example.Main$.(elidable.scala)
at example.Main.main(elidable.scala)

Output from scalac -Xelide-below 1000 elidable.scala && scala example.Main

starting
assertion
off
severe
ending
java.lang.AssertionError: assertion failed: boom!
at scala.Predef$.assert(Predef.scala:93)
at example.Main$.(elidable.scala:34)
at example.Main$.(elidable.scala)
at example.Main.main(elidable.scala)

Output from scalac -Xelide-below 3000 elidable.scala && scala example.Main

starting
off
ending

Scala 2.7 to 2.8 migration help

Scala 2.8 has some very significant differences from Scala 2.7 so if you want to migrate from Scala 2.7 to 2.8 you might want to view this Stack overflow topic:

What are the biggest differences between Scala 2.8 and Scala 2.7?

It has some good tips.

Variant Positions 3

The last few topics all discussed variance in its different forms. The following is a cheat sheet of the where the different variances exist within a class.

See Variant positions 1 for a discussion on one position in a class that is a contravariant position.

The example is:

1. scala> class Output[+A] {def write(a : A) = () /*do write*/ }

In this example A in the method write is an contravariant position. Which means the previous definition is not legal because A is defined as Covariant in the class definition. In a class there are several positions with different variance characteristics. Here's the example from Programming in Scala:

1. abstract class Cat[-T, +U] { 
2.     def meow[W^-](volume: T^-, listener: Cat[U⁺, T^-]^-): Cat[Cat[U⁺, T^-]^-, U⁺]⁺
3. }

If you remove the superscript + and - the above example actually compiles. The + and - indicate if the position is a covariant or contravariant position. Its not critical to memorize the positions (in my opinion). Just look it up as needed. The rule of thumb is that each nested position is inverted (flipped) value of it enclosing position.

That is all I will say about that :)

Working on Scala IO

I just want to let everyone know that I am working hard on a Scala IO library right now and as such I want to dedicate all my spare time to doing that. So (as has been the case lately) I plan to only update the blog 2-3 times a week. Once done with the library I will try to increase the frequency of updates on the blog.


If you have any topics or code snippets you think would be fit good with the block please send them to me at jeichar.w@gmail.com.

Jesse