Scala: Object equality and the canEqual method

This week I'm in chapter 30 of Programming in Scala, 2nd ed., the chapter titled Object Equality.

Getting Object Equality Right

This chapter is about how hard it is to properly implement a class' equals method. There is good advice here on the pitfalls to avoid and recipes to write good equals and hashCode methods. Most of this chapter is present in the article How to Write an Equality Method in Java except that the examples in the article use Java instead of Scala.

What is the canEqual method?

One of the strategies in this chapter is to introduce a canEqual method for non-final classes. This allows subclasses to override canEqual if they want to not allow being equal to the parent class or sibling classes.

The example in the chapter is this. You start with a Point class, which has x and y coordinate members. Then you have a ColoredPoint class that subclasses Point and overrides equals to make it so that ColoredPoints aren't equal to Points.

Here's the definition of Point:

class Point(val x: Int, val y: Int) {
    override def equals(other: Any) = other match {
        case that: Point => this.x == that.x && this.y == that.y
        case _ => false
    }
}

And the naive implementation of ColoredPoint:

class ColoredPoint(x: Int, y: Int, val color: Color.Value) 
    extends Point(x, y) {

    override def equals(other: Any) = other match {
        case that: ColoredPoint => 
            this.color == that.color && super.equals(that)
        case _ => false
    }
}

where Color is:

object Color extends Enumeration {
    val Red, Orange, Yellow, Green, Blue, Indigo, Violet = Value
}

The problem with this is that equals is not symmetric. It is possible for a Point to be equal to a ColoredPoint, but the ColoredPoint wouldn't be equal to the Point.

This is a little better, but still not transitive:

class ColoredPoint(x: Int, y: Int, val color: Color.Value) 
    extends Point(x, y) {

    override def equals(other: Any) = other match {
        case that: ColoredPoint =>
            (this.color == that.color) && super.equals(that)
        case that: Point => that equals this
        case _ => false
    }
}

To see how this doesn't work, consider a red ColoredPoint with x and y coordinates of 1,2 and a blue ColoredPoint with the same coordinates. The red ColoredPoint is equal to a Point(1, 2) and the Point(1, 2) is equal to the blue ColoredPoint, but the red and blue ColoredPoint are not equal to each other.

The solution proposed in the chapter is to introduce a new method, canEqual:

def canEqual(other: Any): Boolean

Point would then be defined as such (including hashCode):

class Point(val x: Int, val y: Int) {

    override def hashCode = 41 * (41 + x) + y
    override def equals(other: Any) = other match {
        case that: Point =>
            (that canEqual this) && 
            (this.x == that.x) && (this.y == that.y)
        case _ => false
    }

    def canEqual(other: Any): Boolean = other.isInstanceOf[Point]
}

And ColoredPoint is defined like so

class ColoredPoint(x: Int, y: Int, val color: Color.Value) extends Point(x, y) {

    override def hashCode = 41 * super.hashCode + color.hashCode
    override def equals(other: Any) = other match {
        case that: ColoredPoint =>
            (that canEqual this) && super.equals(that) && this.color == that.color
        case _ => false
    }

    override def canEqual(other: Any): Boolean = other.isInstanceOf[ColoredPoint]
}

Now Point instances cannot be equal to ColoredPoint instances since the first check that Point.equals will make is to call ColoredPoint.canEqual(Point) which will return false. It's vitally important that the canEqual method be call on that with this as the argument. canEqual is a way for classes to define what they can be equal to. In Point and ColoredPoint the match expression has been used to make sure that that is the right type, so now we can call canEqual on that to make sure that equality is possible in the reverse direction: that that canEqual this.

Does canEqual violate the Liskov Substitution Principle?

One criticism of the canEqual approach is that it violates the Liskov Substitution Principle which, according to Wikipedia, states:

if S is a subtype of T, then objects of type T may be replaced with objects of type S (i.e., objects of type S may substitute objects of type T) without altering any of the desirable properties of that program (correctness, task performed, etc.)

The authors of the book make the argument that Liskov Substitution Principle is not violated because, although the behavior of subclasses is different than the parent class, the contract itself, that equals return a boolean value, is not changed.

My intuition though is that this is a violation. From the perspective of the Point class, any two Point instances at the same x and y coordinates are equal. A subclass changing that definition has violated the contract in a way that makes a subclass not substitutable with a parent class. Let's look at an example of where substitution is violated.

Consider a distance method in Point that calculates the distance between two Points.

def distance(point:Point):Double =
    if (this == point)
        0
    else
        Math.sqrt(Math.pow(this.x - point.x, 2) + Math.pow(this.y - point.y, 2))

This method is taking a shortcut: if the two points are equal, then just return 0. This shortcut won't work if applied to a ColoredPoint even though it could be if ColoredPoint hadn't overridden the equals method. To me this is an example of a case where substitutability is violated because this method is expecting that it can take this shortcut for any Point instance.

canEqual is a code smell

In general I think that canEqual is a code smell. When you look at just the problem of defining equals it might seem reasonable to introduce canEqual. But think about the impact on other methods. For example, consider if we had extended Point with a new 3DPoint class. Then we would have to completely change the distance method. So not only can 3DPoint instances not equal Point instances, but we can't calculate the distance between 3DPoints and Points. This is clearly a Liskov Substitution Principle violation.

So if you are thinking of using canEqual because you want subclasses to not be equal to parent classes, it seems likely to me that if your subclasses can't equal the parent class then that probably affects other methods too.

As an alternative, consider using composition instead of inheritance. For example, we could define the ColoredPoint like so:

class ColoredPoint2(x: Int, y: Int, val color: Color.Value) {

    val point = new Point(x, y)

    override def hashCode = 41 * point.hashCode + color.hashCode
    override def equals(other: Any) = other match {
        case that: ColoredPoint2 =>
            point.equals(that.point) && this.color == that.color
        case _ => false
    }
}

Additional Resources

• How to Write an Equality Method in Java
• Code examples from chapter 30

Scala: Understanding the self type annotation and how it relates to the Cake Pattern

I'm currently working through the book Programming in Scala, 2nd ed.. I'm in chapter 29 which is on Modular Programming Using Objects. What is covered in the chapter has also been referred to as the Cake Pattern. The chapter takes the approach of building up to the Cake Pattern through an example that helps illustrate the kind of problems that the Cake Pattern solves. To understand the Cake Pattern you have to understand how the self type annotation works. So I'm going to take a slightly different approach and start with how the self type annotation works since it is so crucial.

What is the self type annotation?

In brief, the self type annotation allows you to split a trait in two but still refer to things on the second trait as though they are defined in the first trait, basically assuming (well, requiring) that they are mixed in together. For example, the following trait simply prints a greeting at a prompt:

trait Prompter1 {

    val prompt = "> "
    val greeting = "Hello world"

    def printGreeting() {
        println(prompt + greeting)
    }
}

val prompter1 = new Object with Prompter1
prompter1.printGreeting

Now suppose you want to split out the greeting part, maybe so that you can provide greetings for different languages. You could do this:

trait Prompter2 {
    // the self type annotation
    this: GreetingProvider =>

    val prompt = "> "

    def printGreeting() {
        println(prompt + greeting)
        // Next line would work too. 'this' can refer to things within this trait or
        // the declared self type trait
        //println(this.prompt + this.greeting)
    }
}

trait GreetingProvider {

    val greeting = "Hello world"
}

val prompter2 = new Prompter2 with GreetingProvider
prompter2.printGreeting

The code in Prompter2 is exactly the same as in Prompter1 except that there is now a self type annotation which says that this can also refer to GreetingProvider. Also the greeting has moved to a separate trait, GreetingProvider.

Do you need the self type annotation if you take care to always mix in the two traits together? No, because Prompter2 won't even compile and you get this error:

<console>:37: error: not found: value greeting
                println(prompt + greeting)

What happens if you tried to create a new Object and only mixed in Prompter2?

scala> new Object with Prompter2
new Object with Prompter2
<console>:19: error: illegal inheritance;
self-type Prompter2 does not conform to Prompter2's selftype Prompter2 with GreetingProvider
            new Object with Prompter2
                            ^

Does order matter? It doesn't appear to. The following works just fine:

val prompter2backwards = new GreetingProvider with Prompter2
prompter2backwards.printGreeting

If you have a self type annotation, does this only refer to that type? Apparently not. We could just as well have defined Prompter2.printGreeting like so:

def printGreeting() {
    // 'this' can refer to things within this trait or the declared self type trait
    println(this.prompt + this.greeting)
}

So the self type annotation appears to extend what this can refer to.

You can also have multiple traits mixed in for your self type annotation:

this: Foo with Bar with Baz =>

So what does this have to do with the Cake Pattern? We'll get there but for now hopefully you can see that the self type annotation allows you to express a dependency within a trait, a dependency that when satisfied allows one trait to make use of code defined in a separate trait. The Cake Pattern is a Dependency Injection technique that uses self type annotations to express and ultimately fulfill the dependencies between traits.

Applying the Cake Pattern to the examples in chapter 29

Chapter 29 doesn't mention the Cake Pattern and doesn't really apply it. It goes as far as introducing the self type annotation and showing how you can use to refactor a large trait and split it up into several smaller traits.

The chapter presents a Database class that abstracts getting Food and Recipe instances from some sort of backing store. The Database is then split up into three traits: one for FoodCategory methods, one for Food methods and one for Recipe methods. It's not all spelled out in the chapter but you would end up with something that looks like the following:

abstract class Food(val name: String) {
    override def toString = name
}

object Apple extends Food("Apple")
object Orange extends Food("Orange")
object Cream extends Food("Cream")
object Sugar extends Food("Sugar")

class Recipe(
    val name: String,
    val ingredients: List[Food],
    val instructions: String
) {
    override def toString = name
}

trait FoodCategories {
    case class FoodCategory(name: String, foods: List[Food])
    def allCategories: List[FoodCategory]
}

trait Foods {
    def allFoods: List[Food]
    def foodNamed(name: String) =
        allFoods.find(f => f.name == name)
}

trait Recipes {
    def allRecipes: List[Recipe]
}

abstract class Database extends FoodCategories with Foods with Recipes {
}

The book then proceeds to implement Foods and Recipes like so:

trait SimpleFoods extends Foods {
    object Pear extends Food("Pear")
    def allFoods = List(Apple, Pear)
    def allCategories = Nil
}

trait SimpleRecipes extends Recipes { // Does not compile
    object FruitSalad extends Recipe(
        "fruit salad",
        List(Apple, Pear),  // Uh oh
        "Mix it all together."
        )
    def allRecipes = List(FruitSalad)
}

The problem is that SimpleRecipes has a dependency on SimpleFoods. As such Pear is no longer in scope. Self type annotation to the rescue!

trait SimpleRecipes extends Recipes {
    this: SimpleFoods =>

    object FruitSalad extends Recipe(
        "fruit salad",
        List(Apple, Pear),
        "Mix it all together."
        )
    def allRecipes = List(FruitSalad)
}

This all works well enough for such a short example, but in the real world, when you have a database abstraction that has hundreds (or thousands?) of methods for retrieving objects from the database, would this suffice? Because the problem becomes that you will end up mixing all of those methods into the local namespace of your Database class. For example, instead of having a Foods.getAll method even this simple example compels us to having the method called Foods.allFoods.

This is where the Cake Pattern comes in. With the Cake Pattern you wrap your trait in a "component" trait. For example, the FoodCategories trait gets wrapped like so:

trait FoodCategoriesComponent {
    val foodCategories: FoodCategories
    trait FoodCategories {
        case class FoodCategory(name: String, foods: List[Food])
        def allCategories: List[FoodCategory]
    }
}

Likewise for Foods and Recipes:

trait FoodsComponent {
    val foods: Foods
    trait Foods {
        def allFoods: List[Food]
        def foodNamed(name: String) =
        allFoods.find(f => f.name == name)
    }
}

trait RecipesComponent {
    val recipes: Recipes
    trait Recipes {
        def allRecipes: List[Recipe]
    }
}

Now I'll create a SimpleFoodsComponent that implements Foods and FoodCategories (the book implements them together too):

// Implement Foods and FoodCategories at once
trait SimpleFoodsComponent extends FoodsComponent with FoodCategoriesComponent {

    val foods = new Object with SimpleFoods
    val foodCategories = foods
    trait SimpleFoods extends Foods with FoodCategories {
        object Pear extends Food("Pear")
        def allFoods = List(Apple, Pear)
        def allCategories = Nil
    }
}

And now time for the SimpleRecipesComponent. This one will depend on SimpleFoodsComponent:

trait SimpleRecipesComponent extends RecipesComponent {
    this: SimpleFoodsComponent =>

    val recipes = new Object with SimpleRecipes
    trait SimpleRecipes extends Recipes {
        object FruitSalad extends Recipe(
            "fruit salad",
            List(Apple, foods.Pear),
            "Mix it all together."
        )
        def allRecipes = List(FruitSalad)
    }
}

But this time the self type annotation brings foods into scope. So instead of bringing the Foods methods into scope we're just bringing the foods reference (which implements Foods) into scope. I like this since it keeps type members in separate namespaces.

Does it make sense to have a Database abstraction any longer? I'm not sure, but, for completeness, here's how I implemented it.

trait DatabaseComponent extends FoodCategoriesComponent
        with FoodsComponent with RecipesComponent {
    val database: Database

    trait Database extends FoodCategories with Foods with Recipes
}

trait SimpleDatabaseComponent extends DatabaseComponent
        with SimpleFoodsComponent with SimpleRecipesComponent {

    val database = new Database with SimpleFoods with SimpleRecipes
}

I haven't yet talked about the other main piece of the chapter's example, the Browser. As a component it would be defined like so:

trait BrowserComponent {
    this: DatabaseComponent =>

    val browser: Browser

    trait Browser {
        def recipesUsing(food: Food)
        def displayCategory(category: database.FoodCategory)
    }
}

And then it could be implemented with a dependency on the SimpleDatabaseComponent:

trait SimpleBrowserComponent extends BrowserComponent {
    this: SimpleDatabaseComponent =>

    val browser = new Object with SimpleBrowser
    trait SimpleBrowser extends Browser {

        def recipesUsing(food: Food) =
            database.allRecipes.filter(recipe =>
                recipe.ingredients.contains(food))

        def displayCategory(category: database.FoodCategory) {
            println(category)
        }
    }
}

If the Browser is the top level component then you could define it more simply, kind of like how the book does it.

For more information:

• http://jonasboner.com/2008/10/06/real-world-scala-dependency-injection-di/
  • Explains the cake pattern along with alternative approaches, very nice.
• http://www.cakesolutions.net/teamblogs/2011/12/19/cake-pattern-in-depth/
  • A more real world example of the cake pattern

Scala: Extractors

I'm currently working through the book Programming in Scala, 2nd ed.. I'm in chapter 26 which is on Extractors.

What are Extractors?

Earlier in the book case classes were introduced. One of the things you can do with case classes is use them in pattern matching expressions. For example, you might have an Email case class to describe an email address:

case class Email(username:String, domain:String)

def isEmail(e: Any):Boolean = e match {
    case Email(_,_) => true
    case _ => false
}

But what if you are dealing with values that aren't case classes? Extractors allow you to basically define arbitrary match expressions without needing to set up case classes.

To understand extractors I find it helpful to understand their inverse, injections, first. Injections take inputs and produce an output of some type, not unlike a case class constructor. Injections have an apply method. So instead of our Email case class above, we could define a somewhat similar injection like so:

object Email {
    def apply(username: String, domain: String) = user + "@" + domain
}

(This is basically the example given in the book.)

An extractor on the other hand works in the reverse direction. In this case it defines an unapply method that would take a candidate string and, if it is an email address, will return the parts which would correspond to the arguments to the apply method:

object Email {
    def apply(username: String, domain: String) = user + "@" + domain
    def unapply(s: String): Option[(String, String)] = {
        val parts = s aplit "@"
        if (parts.length == 2) Some(parts(0), parts(1)) else None
    }
}

An extractor requires the unapply method, the apply method is optional. Also note that the unapply method returns an Option and will return None if the string is not an email address.

For more details see Extractor Objects. For example, you can have an unapply method that returns a Boolean, and there is the unapplySeq method for handling variable number of arguments to an extractor.

When to use extractors vs case classes?

So extractors let you define match expression patterns in much the same way as can be achieved with case classes. When do you use extractors instead of case classes?

The advantage that extractors have over case classes is that case classes expose the implementation type of an API's data model. Using an extractor allows you to hide the implementation type(s) of the API's data model and change it without requiring client code to change as well.

For example, we can use our Email extractor with a non-case class email class like so:

class EmailImpl(val username:String, val domain:String) {

    override def toString: String = username + "@" + domain
}

object Email {

    def unapply(s: String): Option[(String, String)] = {
        val parts = s split "@"
        if (parts.length == 2) Some(parts(0), parts(1)) else None
    }
}

Case classes do have advantages though. They are simpler, can be optimized better by the Scala compiler and with sealed case class hierarchies the compiler can also catch missed cases.

You can always start with case classes and then switch to extractors once there is a need to change the data model's concrete representation type.

An example: Date

Extractors seem like a great way of working with unstructured data and APIs where you don't have control over the source code. As an example consider the following extractor for getting the individual time values out of a java.util.Date instance:

import java.util.{Calendar => JCal, Date => JDate}

object Date {

    def unapply(d: JDate):Option[(Int,Int,Int,Int,Int,Int,Int)] = {
        val cal = JCal.getInstance
        cal.setTime(d)

        Some(cal get JCal.YEAR,
            cal get JCal.MONTH,
            cal get JCal.DAY_OF_MONTH,
            cal get JCal.HOUR_OF_DAY,
            cal get JCal.MINUTE,
            cal get JCal.SECOND,
            cal get JCal.MILLISECOND)
    }
}

This allows you write match expression against java.util.Date instances, like so:

def isFebruary(d: JDate): Boolean = d match {
    case Date(_, 1, _, _, _, _, _) => true
    case _ => false
}

You can also just use them to unpack values:

val Date(year, month, day, hour, minutes, seconds, milliseconds) = new JDate

Now you have a much simpler way to work with Java date instances.

Final thoughts

Extractors are kind of hard to think about because you have to think in terms of turning output backwards into inputs. Also, it's not always obvious what would be useful for unapply to return. When working through the examples and making up some of my own I found it useful to think of how I would implement the injection (i.e., the apply method) first.

Scala: Encoded Polyline, an Example in Implementing a Custom Collection Type

This week I'm in chapter 25 of Programming in Scala, 2nd ed., the chapter titled The Architecture of Scala Collections.

As an exercise, I decided I'd implement a custom collection for encoded latitude/longitude points using Google's encoding method described here if you're interested. I've written some encoding/decoding code for this format for the FuelMyRoute Android app I've been working on, so I'm fairly familiar with it. The example the authors implement in the book is a RNA collection where the bases are stored as bits in an Array of Ints. In trying to come up with a different data structure to implement I likewise thought of one where the data is stored in a different and more compact format.

So I started by creating a case class to represent a latitude/longitude point, LatLng:

case class LatLng(lat:Double, lng:Double)

Then I created a Polyline class that extends LinearSeq:

class Polyline private (val encoding: String, val initLatLng:LatLng)
  extends LinearSeq[LatLng] {
  ...
}

Why a LinearSeq? Well, the polyline encoding format works like this. You encode the value of the first latitude and longitude point as a character string. For the second point, you encode the difference from the first point. For the third point, you encode the difference from the second point, and so on. So there is no efficient random access possible. Getting the first point (head) is fine, but in general getting a point at some index will take time proportional to the length of polyline. This all strongly suggests LinearSeq as the right abstraction for an encoded polyline. Scala's List has the same performance characteristics, for example, and is also a LinearSeq.

There are two abstract methods that must be implemented by subclasses of LinearSeq: apply and length. Unfortunately, again, these will take time proportional to the length of the polyline. I'm implementing them here based on the iterator:

def apply(idx: Int): LatLng = {
    val it = iterator
    var i = 0
    while (it.hasNext && i <= idx) {

        val latlng = it.next
        if (idx == i)
            return latlng
        else
            i += 1
    }
    throw new IndexOutOfBoundsException("No LatLng at index " + idx)
}

def length: Int = {
    val it = iterator
    var i = 0
    while (it.hasNext) {

        it.next
        i += 1
    }
    i
}

But for a LinearSeq, what you want to do is provide efficient implementations of isEmpty, head and tail. The private constructor for Polyline is given the encoding as a String, as well as the initial values for latitude and longitude, which are 0 for starting from an encoded polyline string. So for isEmpty we can simply check the length of the encoding string:

override def isEmpty: Boolean = encoding.length == 0

head will lazily convert the first latitude/longitude point and return it.

override def head(): LatLng = {

    if (isEmpty) {
        throw new NoSuchElementException("Collection is empty.")
    }

    computeFirstLatLng()
    firstLatLng.get
}

computeFirstLatLng sets firstLatLng, which is of type Option[LatLng].

The way tail will work is this: it will get the first latitude/longitude point and the remainder of the encoded string and then create a new Polyline instance from those values. Recall that when a Polyline is created it is given an initial value for the first latitude/longitude point. We can pass the first LatLng as the initial value to use for the Polyline that includes the substring of the encoded polyline from the second point on.

override def tail(): Polyline = {

    if (isEmpty) {
        throw new UnsupportedOperationException("Collection is empty.")
    }

    computeFirstLatLng()
    new Polyline(encoding.substring(index), firstLatLng.get)
}

Where did index come from? That's a private var in class Polyline that keeps track of the position within the Polyline. It really only ever points to first point (index=0) or the second point, since traversing this Polyline will consist of calling head then tail then head and so on until the returned tail isEmpty. Here's how index is used and how computeFirstLatLng is implemented:

private def computeFirstLatLng() {

    if (firstLatLng.isEmpty && encoding.length > 0) {

        val lat = initLatLng.lat + getNextNumber
        val lng = initLatLng.lng + getNextNumber

        firstLatLng = Some(LatLng(lat, lng))
    }
}

private def getNextNumber():Double = {
    var b = 0
    var shift = 0
    var result = 0

    do {
        b = encoding.charAt(index) - 63
        index += 1
        result |= (b & 0x1f) << shift
        shift += 5
    } while (b >= 0x20)
    return (if ((result & 1) != 0) ~(result >> 1) else (result >> 1)) / 1e5
}

Now to create a companion object that can construct a Polyline instance:

object Polyline {

    def empty: Polyline = new Polyline("", LatLng(0,0))
    def fromEncoding(encoding:String) = new Polyline(encoding, LatLng(0,0))
    def fromSeq(latlngs:Seq[LatLng]):Polyline = {
        // TODO: implement encoding LatLngs into a polyline string
    }
}

Now we can create and iterate over a Polyline instance:

scala> val pl = Polyline.fromEncoding("_p~iF~ps|U_ulLnnqC_mqNvxq`@")
pl: Polyline = (LatLng(38.5,-120.2), LatLng(40.7,-120.95), LatLng(43.252,-126.453))

Builders

This all works well enough, but what happens if you apply methods like take or filter?

scala> pl.take(2)
res0: scala.collection.LinearSeq[LatLng] = List(LatLng(38.5,-120.2), LatLng(40.7,-120.95))

The type of the result is List, not Polyline as we would like. To have your custom Collection type return results in the same type you need to provide a Builder that can construct instances of your custom collection type.

What's a Builder? A Builder can add elements to a particular kind of collection type. Also useful is that a Builder provides a mapResult method that allows you to map from the output of one Builder to a different collection type. Here's a simplified interface:

trait Builder[-Elem, +To] {

    def +=(elem: Elem): this.type
    def result(): To
    def clear()
    def mapResult(f: To => NewTo): Builder[Elem, NewTo]
}

The power of mapResult is we can use an existing Builder to create a collection of one type and then map it to the Polyline collection type. In our case we'll use ArrayBuffer.

So what do you need to do to supply a custom Builder?

1. Extend the "Like" trait and supply the result type of your custom collection as the second type parameter of the trait. Every Seq type has a corresponding "Like" type that contains all of the implementation. For example, LinearSeq's Like type is LinearSeqLike.
2. Override newBuilder to return a Builder that can construct instances of your custom collection type.

For Polyline it would work like this:

class Polyline private (val encoding: String, val initLatLng:LatLng)
    extends LinearSeq[LatLng] with LinearSeqLike[LatLng, Polyline] {

    override def newBuilder: Builder[LatLng, Polyline] =
        new ArrayBuffer[LatLng] mapResult Polyline.fromSeq
    ...
}

Note: I'd need to actually implement Polyline.fromSeq for this to work. I ran out of time, but hopefully you can see how the Builder would work and actually implementing fromSeq is just a detail at this point.

CanBuildFrom

Overriding newBuilder isn't quite enough for our custom collection type to always return the same collection type (at least when it is possible to return the same collection type). For example, the collection concatenation operator, ++, needs to be able to return a sequence where the element type of the sequence is the most specific superclass of the right hand side and left hand side collections. It does this via an implicit parameter of type CanBuildFrom. The signature of ++ is:

def  ++[B >: A, That](that: GenTraversableOnce[B])
    (implicit bf: CanBuildFrom[LinearSeq[A], B, That]): That

CanBuildFrom is a trait defined as such:

trait CanBuildFrom[-From, -Elem, +To] {

    def apply(from: From): Builder[Elem, To]
    def apply(): Builder[Elem, To]
}

So basically the Scala compiler will try to bind the most specific implicit CanBuildFrom that it can match the types of the arguments. LinearSeq defines a very general CanBuildFrom that can be used for any types. To have ++ concatenate two Polylines and return a Polyline instance we have to define a specific CanBuildFrom, which can be done in the companion object:

object Polyline {

    //...

    // We'll move the newBuilder method to the companion object and the
    // Polyline class will reference this one
    def newBuilder: Builder[LatLng, Polyline] =
        new ArrayBuffer[LatLng] mapResult Polyline.fromSeq

    def implicit def canBuildFrom[Polyline, LatLng, Polyline] =
        new CanBuildFrom[Polyline, LatLng, Polyline] {

            def apply(): Builder[LatLng, Polyline] = newBuilder
            def apply(from: Polyline): Builder[LatLng, Polyline] = newBuilder
        }
}

Resources

• The polyline decoding code was largely inspired by http://jeffreysambells.com/2010/05/27/decoding-polylines-from-google-maps-direction-api-with-java
• Looks like most of chapter 25 of Programming in Scala is online: http://docs.scala-lang.org/overviews/core/architecture-of-scala-collections.html

Scala: What's the difference between Traversable and Iterable?

I'm currently working through the book Programming in Scala, 2nd ed.. I'm in chapter 24 and reading about the Traversable and Iterable traits and the difference between them.

Traversable is a trait with one abstract method, foreach. It's signature is

def foreach[U](f: Elem => U)

Defining this one method for a Traversable allows your collection class to gain several useful methods like

• map
• flatMap
• take
• drop
• filter
• foldLeft, foldRight
• etc.

Iterable is a trait that extends Traversable and also has one abstract method, iterator. It's signature is

def iterator: Iterator[A]

Iterable defines foreach in terms of this iterator method:

def foreach[U](f: Elem => U): Unit = {
    val it = iterator
    while (it.hasNext) f(it.next())
}

If we can implement foreach in terms of iterator, why have Traversable as a separate trait?

The book provides one reason: that for some collections, implementing iterator may not be easy or may not be efficient. To illustrate this the book uses a Tree data structure as an example.

The Tree data structure is defined as a case class hierarchy:

sealed abstract class Tree
case class Branch(left: Tree, right: Tree) extends Tree
case class Node(elem: Int) extends Tree

I'm a Scala newbie so I couldn't get their Traversable Tree code example to work. Instead I came up with this:

sealed abstract class Tree extends Traversable[Int]
case class Branch(left: Tree, right: Tree) extends Tree {
  def foreach[U](f: Int => U) = left foreach f; right foreach f
}
case class Node(elem: Int) extends Tree {
  def foreach[U](f: Int => U) = f(elem)
}

For the Iterable version I came up with this:

sealed abstract class Tree extends Iterable[Int]
case class Branch(left: Tree, right: Tree) extends Tree {
  def iterator: Iterator[Int] = left.iterator ++ right.iterator
}
case class Node(elem: Int) extends Tree {
  def iterator: Iterator[Int] = Iterator.single(elem)
}

Both fairly straightforward. The problem with the Iterable version is with the efficiency of visiting nodes in the tree. In particular, the implementation of ++ is such that it has to do an extra indirection at every call to next to determine whether to pull from the left or the right iterator.

I think it helps to see what a naive implementation of ++ would look like:

def ++[A](left:Iterator[A], right:Iterator[A]):Iterator[A] =
    return new Iterator[A] {

        def hasNext: Boolean = left.hasNext || right.hasNext

        def next: A =
            if (left.hasNext)
                left.next
            else
                right.next
    }

Every call to next has to first check left.hasNext before returning a value. In a balanced binary tree with N leaf nodes, the depth of the tree is approximately log(N). So to reach a leaf via this added iterator would require an extra log(N) calls to left.hasNext. Therefore, visiting all of the leaf nodes using the iterator would take O(N*log(N)).

But, that's with the naive implementation of ++. The actual implementation, shown below, optimizes by keeping a reference, cur, to the current Iterator. This allows it to avoid needing to check hasNext on the first Iterator on each call to next.

def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = new AbstractIterator[B] {
    // optimize a little bit to prevent n log n behavior.
    private var cur : Iterator[B] = self
    private var selfExhausted : Boolean = false
    // since that is by-name, make sure it's only referenced once -
    // if "val it = that" is inside the block, then hasNext on an empty
    // iterator will continually reevaluate it. (ticket #3269)
    lazy val it = that.toIterator
    // the eq check is to avoid an infinite loop on "x ++ x"
    def hasNext = cur.hasNext || (!selfExhausted && {
        it.hasNext && {
            cur = it
            selfExhausted = true
            true
        }
    })
    def next() = { hasNext; cur.next() }
}

So, to a certain degree, this example with the Tree is a little artificial. It's just as easy to implement Tree as an Iterable as it is to implement it as a Traversable and there is no fundamental reason why the performance of visiting all of the leaf nodes needs to be worse than a Traversable implementation.

I think it is reasonable to assume that there might be data structures where implementing an Iterator over their elements could be challenging (either fundamentally so or with regards to efficiency). I just wish I could think of a more compelling example.

Further resources:

• http://stackoverflow.com/questions/2602379/in-scala-2-8-collections-why-was-the-traversable-type-added-above-iterable
• http://blog.schauderhaft.de/2010/12/19/the-scala-collection-api-sucks-or-is-it-a-work-of-beauty/