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

NullPointer when mixed traits (Warning)

This tip is mainly to document a 'GOTCHA' that I got caught by recently. It basically goes like this:

Trait Y extends(or has self-type) X. Trait X defines some abstract method 'm'. The initialization code in Y accesses 'm'. Creation of an object new X with Y results in: *Boom* NullPointerException (on object creation).

The example in code:

1. scala> trait X { val x : java.io.File }
2. defined trait X
4. scala> trait Y {self : X => ; val y = x.getName} 
5. defined trait Y
7. scala> new X with Y { val x = new java.io.File("hi")}
8. java.lang.NullPointerException
9. at Y$class.$init$(< console>:5)
10. at $anon$1.< init>(< console>:7)
11. ...

At a glance it seems that x should override the abstract value x in trait X. However the order in which traits are declared is important. In this case first Y is configured then X. Since X is not yet configured Y throws an exception. There are several ways to work around this.
Option 1:

1. trait X {val x : java.io.File}
2. trait Y {self : X => ; val y = x.getName}
3. /*
4. Declaring Y with X will work because Y is initialized after X
5. but remember that there may
6. be other reasons that X with Y is required.  
8. Method resolution is one such reason
9. */
10. new Y with X { val x = new java.io.File("hi")}

Option 2:

1. trait X { val x : java.io.File }
2. trait Y {self : X => ; def y = x.getName}
3. /*
4. Since method y is a 'def' x.getName will not be executed during initialization.
5. */
6. scala> new X with Y { val x = new java.io.File("hi")}
7. res10: java.lang.Object with X with Y = $anon$1@7cb9e9a3

Option 3:

1. trait X { val x : java.io.File }
2. trait Y {self : X => ; lazy val y = x.getName}
3. /*
4. 'lazy val' works for the same reason 'def' works: x.getName is not invoked during initialization
5. */
6. scala> new X with Y { val x = new java.io.File("hi")}
7. res10: java.lang.Object with X with Y = $anon$1@7cb9e9a3

Option 4:

1. trait X {val x : java.io.File }
2. trait Y extends X {def y = x.getName}
3. /*
4. if Y extends X then a new Y can be instantiated
5. */
6. new Y {val x = new java.io.File("hi")}

Two more warnings. First, the same error will occur whether 'x' is a def or a val or a var.

1. trait X { def x : java.io.File }   
2. trait Y {self : X => ; val y = x.getName}     
3. new X with Y { val x = new java.io.File("hi")}

Second warning: In complex domain models it is easy to have a case where Y extends X but the final object is created as: new X with Y{...}.

You will get the same error here because (I think) the compiler recognized that Y is being mixed in with X and therefore the X will be initialized as after Y instead of before Y.

First the code:

1. trait X { def x : java.io.File }   
2. trait Y extends X { val y = x.getName}        
3. new X with Y { val x = new java.io.File("hi")}

If the code instantiated new Y{...} the initialization would be X then Y. Because X can only be initialized once, the explicit declaration of new X with Y forces Y to be initialized before X. (X can only be initialized once even when it appears twice in the hierarchy).

This is a topic called linearization and will be addressed in the future.

Using objects to access trait functionality

Today's topic is based on an article by Bill Venners. http://www.artima.com/scalazine/articles/selfless_trait_pattern.html. I recommend reading that article as it goes into much more detail. I also recommend taking a look at the earlier topic that covers companion objects.

The normal way to use a trait is to mix it in to an object. However there can be a problem mixing two traits containing methods with equal signatures. If the two traits are not designed to work together then you will get a compile error. Otherwise one method will override the other. Either way you cannot access both methods. There is an additional way to access the functionality of a trait. You can create an object (not instance) that extends the trait and import the methods when you need them.

If the trait is stateless then the object can be shared if not then make sure that sharing the object is carefully handled.

Examples:

1. scala> trait T1 {
2.      | def talk = "hi"
3.      | }
4. defined trait T1
6. scala> trait T2 {
7.      | def talk = "hello"
8.      | }
9. defined trait T2
11. // Cannot extend C with T1 and T2 because they are not designed to work together
12. scala> class C extends T1 with T2
13. :6: error: error overriding method talk in trait T1 of type => java.lang.String;
14.  method talk in trait T2 of type => java.lang.String needs override modifier
15.        class C extends T1 with T2
16.              ^
18. scala> class C extends T1
19. defined class C
21. // objects can have state so becareful how you share them
22. scala> object Obj1 extends T1
23. defined module Obj1
25. scala> object Obj2 extends T2
26. defined module Obj2
28. // You can give aliases to the imported methods and use them in the class
29. scala> class C {
30.      | import Obj1.{talk => hi}
31.      | import Obj2.{talk => hello}
32.      | def sayHi = hi
33.      | def sayHello = hello
34.      | }
35. defined class C
37. scala> val c = new C
38. c: C = C@54d8fd1a
40. scala> c.sayHi
41. res0: java.lang.String = hi
43. scala> c.sayHello
44. res1: java.lang.String = hello
46. scala> class C extends T1 {
47.      | import Obj2.{talk => hello}
48.      | def helloTalk = hello
49.      | }
50. defined class C
52. scala> val c2 = new C
53. c2: C = C@2ee634bf
55. scala> c2.talk
56. res2: java.lang.String = hi
58. scala> c2.helloTalk
59. res5: java.lang.String = hello

Adding methods using Traits

One useful application of a trait is the case where you want to add functionality to an existing class. In this example I have a class provided by a third party library (in this just a simple StringReader class from the Java library). But I want to be able to read lines as well as use the standard read methods.

One solution is to create a trait and when I instantiate the StringReader mix in the new trait. Code like new StringReader() with Lines results in a new class that extends StringReader and the trait Lines. As a result we have all the methods of StringReader and Lines. The biggest benefit is that we can define the trait to work with any Reader and then when we create the real instance we can mix it in to any class that extends Reader.

The other solution that can be used is to create an implicit conversion from StringReader to some other class. There are two draw backs here:

• It is harder to tell what is happening
• A trait can contain state but a "view" (which is what you get when one class is implicitly converted to another class) has no state it is just a view of the original class. In this example a view would work but in other examples like creating a pushback reader, it would not work.

Here is a simple example:

1. scala> trait Lines {
2.      | // the self type declares what type of class the trait can be applied to
3.      | // if there is no self type then it is assumed it can be applied to Any type
4.      | self:java.io.Reader =>
5.      | def nextLine:Option[String] = {
6.      | val builder = new scala.collection.mutable.StringBuilder()
7.      |
8.      | var next = read()
9.      |
10.      | while( next != -1 && next.toByte.toChar != '\n' ){
11.      | builder += next.toByte.toChar
12.      | next = read()
13.      | }
14.      |
15.      | if( builder.isEmpty ) None
16.      | else Some(builder.toString)
17.      | }
18.      | }
19. defined trait Lines
21. // Strings starting and ending with (""") are called raw strings.  All characters 
22. // within """ """ are automatically escaped.
23. // I am creating a reader and mixing in the Lines trait on construction
24. scala> val reader = new java.io.StringReader( """line one
25.      | line two""" with Lines
26. reader: java.io.StringReader with Lines = $anon$1@3850620f
28. scala> reader.nextLine
29. res0: Option[String] = Some(line one)
31. scala> reader.nextLine
32. res1: Option[String] = Some(line two)
34. scala> reader.nextLine
35. res2: Option[String] = None
37. scala> reader.nextLine
38. res3: Option[String] = None
40. // we can define a method that takes a reader with lines
41. scala> def toCollection( reader:java.io.StringReader with Lines) = {
42.      | def collect:List[String] = reader.nextLine match {
43.      |   case None => Nil
44.      |    // we do not need to worry about stack overflow
45.      |    // because of tail recursion.  This method cannot be
46.      |    // extended and collect is the last like in the collect
47.      |    // method so this method will be transformed into a loop
48.      |   case Some( line ) => line :: collect
49.      | }
50.      |
51.      | collect
52.      | }
53. toCollection: (reader: java.io.StringReader with Lines)List[String]
55. scala> toCollection( new java.io.StringReader( "line one\nlinetwo" ) with Lines).size
56. res8: Int = 2

Traits and inheritance

Scala provides two structures for inheritance. Classes (abstract or not) and traits. Traits are very similar to Ruby Mixins meaning that they can contain code like abstract classes but like interfaces multiple traits can be inherited from.
Like interfaces traits cannot have constructors but in Scala variables can be abstract and therefore provide an easy way to simulate a constructor.
There are no method resolution conflicts because method definitions are always resolved right to left:

1. class X extends Y with A with B with C

If ABC and Y all have the method (doit) the method in C will be used. If C calls super.doit that will call B.doit and so on.
Note: If Y defines doit the A, B, and C must define doit with the override keyword:

1. override def doit() = {...}

In the above example ABC must be traits but Y can be a class or a trait. When inheriting you must always have one extends keyword which can optionally followed by one or more with clauses.

1. scala> abstract class Animal {
2.      |  val legs:Int
3.      | val noise:String
4.      | def makeNoise() = println(noise)
5.      | }
6. defined class Animal
8. scala>  trait Quadriped {
9.      | self:Animal =>
10.      | val legs = 4
11.      | }
12. defined trait Quadriped
14. scala> trait Biped {
15.      | self:Animal =>
16.      | val legs = 2
17.      | }
18. defined trait Biped
20. scala> class Dog extends Animal with Quadriped {
21.      | val noise = "Woof"
22.      | override def makeNoise() = println( noise+" "+noise)
23.      | }
24. defined class Dog
26. scala> new Dog().makeNoise()
27. Woof Woof
29. scala> abstract class GenericAnimal extends Animal{ 
30.      | val noise = "glup"                          
31.      | }
32. defined class GenericAnimal
34. scala> val quad = new GenericAnimal() with Quadriped
35. quad: GenericAnimal with Quadriped = $anon$1@10bfb545
37. scala> quad.makeNoise()
38. glup
40. scala> val biped = new GenericAnimal() with Biped
41. biped: GenericAnimal with Biped = $anon$1@7669521
43. scala> val biped = new GenericAnimal() with Biped{
44.      | override val noise = "Hello"
45.      | }
46. biped: GenericAnimal with Biped = $anon$1@6366ce5f
48. scala> biped.makeNoise()
49. Hello