Equality & Scala 3

This one is a quickie. I forgot -- again -- to mention that Scala does provide a way around having to define your own equals method. To be more specific, case classes come with reasonably defined equals methods.

Equality & Scala 2

My efforts, yesterday, to come up with an Equatable trait that could ease a bit the knowledge and sheer drudgery of making a valid “equals” method met with unexpected difficulties. While tempted to replace the incorrect code with a correct one before the article got many hits, I decided that the problems I encountered and the mistakes I made taught a lesson by itself.

Anyway, I'd like first to make a few remarks that were missing from that post. One thing to notice here is that while this trait might be useful to some people, it is slower than a well thought-out equals definition. What I'm trying to do is see how much Scala let me make the job of creating valid equals methods both easier and safer.

It all comes down to the idea that, being equality in languages with subclassing so full of pitfalls, and the general solution to it being a well-defined pattern, those languages ought to be doing something about it at the language level. Or library level, if possible.

It does cross my mind that this problem might be much more efficiently and elegantly solved in languages which makes it possible to generate code at compile time, such as Lisp with its macros, and Ruby with access to the AST. This is one thing I miss in Scala, and while I understand the reasons for it and empathize with them, I do come up some roadblocks to a scalable language now and then.

That said, let’s analyze what happened. I tried to model my trait after the Hashable class. There are two things, though, that made my job harder than Hashable’s. First, I depended on super.equals, while hashCode doesn’t depend on its super. This becomes important as super.equals would make reference to definitions such as testSuperEquals or equateValues, and these definitions would be overridden in the subclass. Therefore, when Point3D.equals called Point.equals (its super.equals), the method Point.equals would make use of Point3D.equateValues and Point3D.testSuperEquals instead of Point.equateValues and Point.testSuperEquals.

This is difficult enough to get around, but it gets worse because, as opposed to hashCode, equals has to reference not one, but two objects. Calling a super of oneself is easy. Not so calling a super to a method on another object.

Another problem is the warning about type erasure. The case match never tests for type "This", so it is necessary to resort to reflection, to make sure we don't try to assign a superclass to a subclass. I didn't get any error on that because the hash test was returning false first. Well, fixed that, and changed the test code to produce constant hashCode.

The goal, then, is to make equals independent on any definition that might get overridden by later equals. Or, in other words, independent of any other definition related to the trait Equatable itself. Of course, it still will need to access members of the other object, and those might get overridden. That, however, is expected and shouldn’t have any influence on the equals method.

To begin with, let’s think how our equals definition would look like in the class. In the next to last definition, we had this:

override def equals(other : Any) = equalsTo[Point](other, true)

where equals was defined as

protected def equalsTo[This <: Equatable](other : Any, superEquals : => Boolean) : Boolean

This definition delegates to the class the task of calling super.equals – or passing “true” if not appropriate. We can’t do that inside equalsTo, because the equalsTo method is never overridden. “Super”, inside it, will have only one meaning. So this solution will do.

Now, how do we deal with equateValues? One obvious solution would be doing this:

protected def equalsTo[This <: Equatable](other : Any, equateValues : Seq[Any], superEquals : => Boolean) : Boolean

There are at least two reasons this isn’t going to work. First, while it solves the problem of equateValues on “this” object, as it get passed as a parameter on equals’ definition, it doesn’t solve it for “that” object! In fact, we now have no way of finding out what are the elements to be compared in the other object.

A second problem, though, might not be as obvious. We might depend on mutable data or data which isn’t computed yet at the time we define equals. Getting around that is possible, but would be much worse than defining an equals method by oneself!

So, what we’ll do is pass a function instead. A function which, given a “that” object, returns the sequence we need. Or, in other words, we want a object of this type:

(that : This) => Seq[Any]

The only problem with that is that “this” inside our trait does not have type This. We’ll need to receive a reference to ourselves, properly typed! Our definition, then, should be:

protected def equalsTo[This <: Equatable](self : This, other : Any, equateValues : This => Seq[Any], superEquals : => Boolean) : Boolean

The body of our function, then, becomes:

(other : @unchecked) match {
    case that : This =>
      (
        that.canEqual(this)
        && superEquals
        && hashCode == that.hashCode // Can speed up or slow down 
        && equateValues(self).zip(equateValues(that)).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }}
}

Now, how would our equals definition look like? Here:

override def equals(other : Any) = equalsTo[Point](this, other, that => List(that.x, that.y), true)
override def equals(other : Any) = equalsTo[Point3D](this, other, that => List(that.z), super.equals(other))

For big objects, inserting the function in the parameters might be awkward. Instead, we might prefer to assign the function to a val first. For example:

private val pointValues = (that : Point) => List(that.x, that.y)

So, here’s everything together, with a bit of further editing for performance resons:

trait Equatable extends scala.util.Hashable {
  def canEqual (that : Any) : Boolean
  
  protected def equalsTo[This <: Equatable](self : This, other : Any, equateValues : This => Seq[Any], superEquals : => Boolean) : Boolean = 
    (other : @unchecked) match {
      case that : This if self.getClass.isAssignableFrom(that.getClass) =>
        // Testing for hash code can improve or decrease performance, depending on the implementation;
        // if hashCode gets implemented as a val, it will make equality faster
        if (that.canEqual(this) && superEquals && hashCode == that.hashCode) {
          val thisValues = equateValues(self)
          val thatValues = equateValues(that)
          (thisValues.zip(thatValues).foldLeft(true) { (equals, tuple) => equals && tuple._1 == tuple._2 } 
           && thisValues.size == thatValues.size)
        } else false
      case _ => false
    }
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  // override def hashValues = List(x, y)
  override def hashValues = List(0) // We don't want the hash skipping our tests
  
  // Equatable definitions
  private val pointValues = (that : Point) => List(that.x, that.y) // one way
  override def equals(other : Any) = equalsTo[Point](this, other, pointValues, true)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  // override def hashValues = List(x, y, z)
  override def hashValues = List(0) // We don't want the hash skipping our tests

  // Equatable defintions
  // private val point3DValues = (that : Point3D) => List(that.z)
  override def equals(other : Any) = equalsTo[Point3D](this, other, that => List(that.z), super.equals(other))
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
}

And the tests. I thought about doing them as assertions, but it was too silent for my taste. Anyway,

scala> val x = new Point(1, 2); val x2 = new Point(1, 2)
x: Point = (1, 2)
x2: Point = (1, 2)

scala> x == x2 // super.equals does not get called, so we do not perform reference equality
res0: Boolean = true

scala> val y = new Point(2, 1)
y: Point = (2, 1)

scala> x == y // expected false
res1: Boolean = false

scala> val z = new Point3D(1, 2, 0)
z: Point3D = (1, 2, 0)

scala> x == z // false in that canEqual this test
res2: Boolean = false

scala> z == x // false through reflection isAssignableFrom
res3: Boolean = false

scala> val z2 = new Point3D(2, 1, 0)
z2: Point3D = (2, 1, 0)

scala> z == z2 // expected false
res4: Boolean = false

scala> val z3 = new Point3D(1, 2, 0)
z3: Point3D = (1, 2, 0)

scala> z == z3 // expected true
res5: Boolean = true

scala> val z4 = new Point3D(1, 2, 1)
z4: Point3D = (1, 2, 1)

scala> z == z4 // extected false
res6: Boolean = false

scala> x == x
res7: Boolean = true

Equality & Scala

I'm just through reading three different sources on equality in less than a week. They all said pretty much the same thing, with a minor variation here or there. It got me thinking about it, and I have some thoughts to share. For this discussion, I'll assume you are familiar with how to do equality correctly. My examples follow the model given in this article.

Let's start with two simple classes:

class Point (val x : Int, val y : Int) {
 override def toString = "(%d, %d)" format (x, y)
}

class Point3D (x : Int, y : Int, val z : Int) extends Point(x,y) {
  override def toString = "(%d, %d, %d)" format (x, y, z)
}

Now, a proper equality method in these classes would look like the following:

class Point (val x : Int, val y : Int) {
  override def toString = "(%d, %d)" format (x, y)
  override def hashCode = 41 * (41 + x) + y
  override def equals(other : Any) : Boolean = 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]
}

class Point3D (x : Int, y : Int, val z : Int) extends Point(x,y) {
  override def toString = "(%d, %d, %d)" format (x, y, z)
  override def hashCode = 41 * (41 * (41 + x) + y) + z
  override def equals(other : Any) : Boolean = other match {
    case that : Point3D => (
      that.canEqual(this)
      && super.equals(that)
      && this.z == that.z
    )
    case _ => false
  }
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
}

Now, Scala has, starting with version 2.8, a Hashable trait, with which we can simplify things:

class Point (val x : Int, val y : Int) extends scala.util.Hashable {
  override def toString = "(%d, %d)" format (x, y)
  override def hashValues = List(x, y)
  override def equals(other : Any) : Boolean = 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]
}

class Point3D (x : Int, y : Int, val z : Int) extends Point(x,y) {
  override def toString = "(%d, %d, %d)" format (x, y, z)
  override def hashValues = List(x, y, z)
  override def equals(other : Any) : Boolean = other match {
    case that : Point3D => (
      that.canEqual(this)
      && super.equals(that)
      && this.z == that.z
    )
    case _ => false
  }
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
}

While it doesn't seem to have gained us anything, it might for larger objects, and, at any rate, it removes the "magic" of a hash code, and let someone else worry how to do it.

Still, there's a lot of stuff in there just to get equality right, and these are pretty simple classes. What we see is a programming pattern, but one so common and so important that, in my opinion, it merits special attention from the language itself.

Barring that, let's see what we can do programmatically about it. I'll start with a helper function, and how it would be used:

def testEquality(one : AnyRef, other : AnyRef, elementsOne : Seq[Any], elementsOther : Seq[Any]) : Boolean = {
  val classOfOne = one.getClass
  val classOfOther = other.getClass

  def sameClassOrSubclass: Boolean = classOfOne.isAssignableFrom(classOfOther)

  def superEquals : Boolean = try {
    val superEqualsMethod = classOfOne.getSuperclass.getMethod("equals", classOf[Any])
    if (superEqualsMethod.getDeclaringClass != classOf[Any])
      superEqualsMethod.invoke(one, other) match {
        case flag : java.lang.Boolean => flag.booleanValue // Translate boxed boolean into boolean
        case _ => error("Method equals on the parent class of object " + one + " does not return a boolean")
      }
    else true
  } catch {
    case _ => true
  }

  def canEqual : Boolean = try {
    val canEqualMethod = classOfOther.getMethod("canEqual", classOf[Any])
    canEqualMethod.invoke(other, one) match {
      case flag : java.lang.Boolean => flag.booleanValue // Translate boxed boolean into boolean
      case _ => error("Method canEqual on object " + other + " does not return a boolean")
    }
  } catch {
    case _ => true
  }

  def elementsEquals : Boolean = {
    elementsOne.zip(elementsOther).foldLeft(true) {
      (equals, pair) => equals && pair._1 == pair._2
    } && elementsOne.size == elementsOther.size
  }

  (sameClassOrSubclass(classOfOne, classOfOther)
    && canEqual
    && superEquals
    && elementsEquals
  )
}

class Point (val x : Int, val y : Int) extends scala.util.Hashable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable
  override def hashValues = List(x, y)

  // Equality
  override def equals(other : Any) : Boolean = other match {
    case that : Point => testEquality(this, that, List(x, y), List(that.x, that.y))
    case _ => false
  }
  def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable
  override def hashValues = List(x, y)

  // Equality
  override def equals(other : Any) : Boolean = other match {
    case that : Point3D => testEquality(this, that, List(x, y, z), List(that.x, that.y, that.z))
    case _ => false
  }
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
}

Now, this method always calls the parent's equals, unless it's Any's equals. You might want to parametrize this. Also, it expects canEqual to be defined if needed, which might lead to bugs. Furthermore, its usage of reflection makes it slower than needed. Finally, the definition of equals is not that much simpler than what we had before.

So, can we do better? Ideally, one could build a trait similar to Hashable, but it turns out that is not that simple. Let's try:

trait Equatable extends scala.util.Hashable {
  protected type EquateThis <: Equatable
  private def equalsFromAny : Boolean = {
    this.getClass.getSuperclass.getMethod("equals", classOf[Any])
    .getDeclaringClass == classOf[Any]
  }

  protected def equateValues : Seq[Any]

  def canEqual (that : Any) : Boolean = true

  abstract override def equals(other : Any) : Boolean = (other : @unchecked) match {
    case that : EquateThis =>
      (
        that.canEqual(this)
        && (equalsFromAny || super.equals(that))
        && hashCode == that.hashCode // Can speed up or slow down
        && equateValues.zip(that.equateValues).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  override def hashValues = List(x, y)

  // Equatable definitions
  override type EquateThis = Point
  override def equateValues = List(x, y)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  override def hashValues = List(x, y, z)

  // Equatable defintions
  override type EquateThis = Point3D
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
  override def equateValues = List(z)
}

That looks more like it, but it has a few problems still. It still uses reflection, for one thing, to test for super's equals method. Also, you can't parametrize that is it is. It won't get Equatable's own equals, though, as traits compiles down to part of the class being defined, not as an ancestor to it.

Next, it has a default for canEqual, and a dangerous one at that. If the programmer forgets to override it, it will lead to trouble.

But, most importantly, it doesn't work. The class Point3D can't override Point's definition for type EquateThis. I don't understand precisely why this is the case, and I'd be glad if anyone stepped in to explain this.

Anyway, let fix these problems:

trait Equatable extends scala.util.Hashable {
  protected def testSuperEquals : Boolean
  protected def equateValues : Seq[Any]
  def canEqual (that : Any) : Boolean

  protected def equalsTo[This <: Equatable](other : Any) : Boolean = (other : @unchecked) match {
    case that : This =>
      (
        that.canEqual(this)
        && ((!testSuperEquals) || super.equals(that))
        && hashCode == that.hashCode // Can speed up or slow down
        && equateValues.zip(that.equateValues).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  override def hashValues = List(x, y)

  // Equatable definitions
  override def testSuperEquals = false
  override def equateValues = List(x, y)
  override def equals(other : Any) = equalsTo[Point](other)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  override def hashValues = List(x, y, z)

  // Equatable defintions
  override def testSuperEquals = true
  override def equals(other : Any) = equalsTo[Point3D](other)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
  override def equateValues = List(z)
}

This finally get us where we wanted. Or as close to as I could, at least. :-)

The definition of canEqual is made abstract. That forces the first class to mix Equatable in to define it, even if to a default of "true". Next, instead of trying to figure out if equality must be called on the super, we simply require the class to tell us.

Finally, the equals method. We can't (or I couldn't) get the trait to define it, but I got pretty close. In the end, class still has to define an equals method, but that method pretty much gets reduced to a simple call to one defined in the trait, passing the object being compared to and the class expected. The class expected gets passed as an explicit type parametrization.

Neat. I didn't think I'd be able to get this much! Now, who's going to port it to Java?

Update:

Ok, I spoke too soon. This method fails here:

scala> val x = new Point(1, 2); val x2 = new Point(1, 2)
x: Point = (1, 2)
x2: Point = (1, 2)

scala> x == x2 // super.equals does not get called, so we do not perform reference equality
res7: Boolean = true

scala> val y = new Point(2, 1)
y: Point = (2, 1)

scala> x == y // expected false
res8: Boolean = false

scala> val z = new Point3D(1, 2, 0)
z: Point3D = (1, 2, 0)

scala> x == z // false in the canEqual call
res9: Boolean = false

scala> z == x // false in the type check
res10: Boolean = false

scala> val z2 = new Point3D(2, 1, 0)
z2: Point3D = (2, 1, 0)

scala> z == z2 // false in the super.equals call
res11: Boolean = false

scala> val z3 = new Point3D(1, 2, 0)
z3: Point3D = (1, 2, 0)

scala> z == z3 // false in the super.super.equals call - it should have been true
res12: Boolean = false

Anyone up for fixing it?

Update 2:

Ok, I fixed it. I resorted to delegating this task to the calling class. That means I do away with testSuperEquals, but require a second parameter to equalsTo. I make it by name, so that it doesn't get evaluated needlessly.

trait Equatable extends scala.util.Hashable {
  protected def equateValues : Seq[Any]
  def canEqual (that : Any) : Boolean
  
  protected def equalsTo[This <: Equatable](other : Any, superEquals : => Boolean) : Boolean = (other : @unchecked) match {
    case that : This =>
      (
        that.canEqual(this)
        && superEquals
        && hashCode == that.hashCode // Can speed up or slow down 
        && equateValues.zip(that.equateValues).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }}
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  override def hashValues = List(x, y)
  
  // Equatable definitions
  override def equateValues = List(x, y)
  override def equals(other : Any) = equalsTo[Point](other, true)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  override def hashValues = List(x, y, z)

  // Equatable defintions
  override def equals(other : Any) = equalsTo[Point3D](other, super.equals(other))
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
  override def equateValues = List(z)
}

And the testing:

scala> val x = new Point(1, 2); val x2 = new Point(1, 2)
x: Point = (1, 2)
x2: Point = (1, 2)

scala> x == x2 // super.equals does not get called, so we do not perform reference equality
res105: Boolean = true

scala> val y = new Point(2, 1)
y: Point = (2, 1)

scala> x == y // expected false
res106: Boolean = false

scala> val z = new Point3D(1, 2, 0)
z: Point3D = (1, 2, 0)

scala> x == z // false in the canEqual call
res107: Boolean = false

scala> z == x // false in the type check
res108: Boolean = false

scala> val z2 = new Point3D(2, 1, 0)
z2: Point3D = (2, 1, 0)

scala> z == z2 // false in the super.equals call
res109: Boolean = true

scala> val z3 = new Point3D(1, 2, 0)
z3: Point3D = (1, 2, 0)

scala> z == z3 // expected true
res110: Boolean = true

Update 3:

This is still seriously broken, as the very test above indicates. What is happening is that when super.equals gets called, it uses this.equateValues instead of the super's version of it. It might be easy to fix for "this", but not for "that". At this point, I'm giving up on super.equals. Let's assume the equality for all classes is defined by the equalsTo method, and require a call to super.equateValues at every subclass (that finds it necessary). Here it is

trait Equatable extends scala.util.Hashable {
  protected def equateValues : Seq[Any]
  def canEqual (that : Any) : Boolean
  
  protected def equalsTo[This <: Equatable](other : Any) : Boolean = (other : @unchecked) match {
    case that : This =>
      (
        that.canEqual(this)
        && hashCode == that.hashCode // Can speed up or slow down 
        && equateValues.zip(that.equateValues).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }}
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  override def hashValues = List(x, y)
  
  // Equatable definitions
  override def equateValues = List(x, y)
  override def equals(other : Any) = equalsTo[Point](other)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  override def hashValues = List(x, y, z)

  // Equatable defintions
  override def equals(other : Any) = equalsTo[Point3D](other)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
  override def equateValues = z :: super.equateValues
}

And test:

scala> val x = new Point(1, 2); val x2 = new Point(1, 2)
x: Point = (1, 2)
x2: Point = (1, 2)

scala> x == x2 // super.equals does not get called, so we do not perform reference equality
res138: Boolean = true

scala> val y = new Point(2, 1)
y: Point = (2, 1)

scala> x == y // expected false
res139: Boolean = false

scala> val z = new Point3D(1, 2, 0)
z: Point3D = (1, 2, 0)

scala> x == z // false in the canEqual call
res140: Boolean = false

scala> z == x // false in the type check
res141: Boolean = false

scala> val z2 = new Point3D(2, 1, 0)
z2: Point3D = (2, 1, 0)

scala> z == z2 // expected false
res142: Boolean = false

scala> val z3 = new Point3D(1, 2, 0)
z3: Point3D = (1, 2, 0)

scala> z == z3 // expected true
res143: Boolean = true

Using Implicits to Select Types

Scala 2.8's collection revision is doing interesting things. The most obvious one will be the methods revision. One thing that shouldn't be all that obvious, though, is how much code will be shared, and how that shared code will still look like it was specific to a class.

I'll quote here a couple of examples from the Scala 2.8 Collection's Whitepaper (pdf at the bottom):

scala> "abc" map (x => (x + 1).toChar)
res1: scala.runtime.RichString = bcd

scala> "abc" map (x => (x + 1))
res2: scala.collection.immutable.Vector[Int] = Vector(98, 99, 100)

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

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

Now, this "map" method is inherited from a common trait, and yet it knows when the result of a map over a RichString is a RichString, when the result of a map over a Map is a Map, and when it's not. How can it be?

The answer is implicit parameters. One thing about implicits, is that a more specific implicit has preference over a more generic one. Take a look at this example:

scala> abstract class X[T] { def id : Unit }
defined class X

scala> implicit def a[T] = new X[T] { def id = println("generic") }
a: [T]X[T]

scala> implicit def b = new X[Int] { def id = println("Int") }
b: X[Int]

scala> def f[T](a : T)(implicit g : X[T]) = g.id
f: [T](T)(implicit X[T])Unit

scala> f(5)
Int

scala> f('c')
generic

Both "a" and "b" have the correct type, X[T]. The second definition, though, will return X[Int], which is more specific than X[T], which the first definition returns. So, whenever X[Int] is required, "b" will take precedence over "a". Naturally, if some other type of X is required, "b" won't be used at all.

This is how map can do its trick. To compose the result, it uses methods from the class Builder[-Elem, +To]. Such a build will create a collection of type To from elements of type Elem. Now, this is not enough to solve map's problem. For example, I want a RichString as result, if I'm doing a map over a RichString, but not if I'm mapping over a List of Chars. See the two examples below:

scala> "abc" map (x => (x + 1).toChar)
res1: scala.runtime.RichString = bcd

scala> List('a', 'b', 'c') map (x => (x + 1).toChar)
res11: List[Char] = List(b, c, d)

So, for methods with more complex semantics, like map, we need something else which can produce the correct Builder. For that, the trait BuilderFactory[Elem,

+To, From] exists. BuilderFactory will produce a Builder for a method which takes a collection of type From, and uses elements of type Elem to produce a collection of type To.

Now, the more generic implicit for a BuilderFactory is BuilderFactory[A, Iterable[A], Iterable[_]], which should be pretty obvious. Other implicits exists, though, such as BuilderFactory[Char, RichString, RichString]. Now, look at map's declaration:

def map[B, That](p: Elem => B)(implicit bf: BuilderFactory[B, That, This]): That

So, when you do "abc".map( x => (x + 1).toChar), the compiler knows that "B" is Char (the result of the function being mapped). "This" is known to be RichString, from the definition of class RichString itself. Now, given that "B" = Char and "This" = RichString, then BuilderFactory[Char, RichString, RichString] is a more specific match than the other implicit definitions. And, because it gets used, "That" gets defined to be RichString also, thus defining the result type for that map.

The cleverness of it is to use implicits to define unknown type parameters as a function of known type parameters. This is can be a very useful pattern for those who want to take maximum advantage of static type checking.