I thought I’d write up a few notes on how type inference and implicit search work together in Scala, as best I understand it. I haven’t seen anyone write this up before: it’s either not in the Scala Language Specification. Or, I can’t parse it out of the spec.

The basic problem is as follows: suppose I have a method like sin. I want it to be generic, so that other people can provide implementations, and things compose, etc. That is, I’d like the following to work:

sin(0.0)
sin(DenseVector(0.0))
sin(DenseMatrix(0.0))
// and in a downstream library
class MyVector extends Vector[Double] { ... }
sin(new MyVector)

Because we want to support downstream extension, we can’t just do raw overloading. Instead, we’re going to try to use type classes/implicits:

def sin[In, Out](x: In)(implicit canSin: CanSin[In, Out]):Out = canSin(x)

trait CanSin[Input, Output] {
  def apply(x: Input):Output
}

Great! Now for vectors and matrices… Ideally, we’d like to be able to support anything that supports map, or at least make it possible for anything that supports map to be used. In Breeze, we have a trait CanMapValues for mappable things:

trait CanMapValues[From, FromElement, ToElement, To] {
  def map(from: From, f: FromElement=>ToElement):To
}

implicit def cmvDenseVector[T, U]:CanMapValues[DenseVector[T], T, 
                                                 U, DenseVector[U]] = ???

I could call it a functor or something, but eh. This lets us write:

implicit def canSinMapValues[From, T, U, To]
         (implicit canSinT: CanSin[T, U],
                   cmv: CanMapValues[From, T, U, To]):CanSin[From, To] = ???

This says that I can execute Sin on anything that can be mapped with one of Sin’s other implementation. Perfect! Except this doesn’t work:

scala> sin(DenseVector(3.0))
<console>:12: error: diverging implicit expansion for type CanSin[Double,Output]
starting with method canSinMapValues
              sin(DenseVector(3.0))

Why is this “diverging”? Well, there’s left recursion in the canSinMapValues implicit: if we want to find an implicit for canSinT, we can look at canSinMapValues, which means we need to find an implicit for canSinT, which means… Ok, fair enough, that is kind of tricky for a compiler to figure out. Well, what if we rearrange the implicits a little:

implicit def canSinMapValues[From, T, U, To]
      (implicit cmv: CanMapValues[From, T, U, To],
                canSinT: CanSin[T, U]):CanSin[From, To] = ???

That way, Scala can figure out the From and the T up front, which will cut off the infinite recursion. Let’s try that:

scala> sin(DenseVector(3.0))
<console>:14: error: could not find implicit value for parameter canSin: CanSin[DenseVector[Double],Output]
              sin(DenseVector(3.0))

Sigh. Why not? Let’s ask Mr. -Xlog-implicits:

<console>:22: canSinMapValues is not a valid implicit value for CanSin[breeze.linalg.DenseVector[Double],Output] because:
hasMatchingSymbol reported error: type mismatch;
 found   : breeze.linalg.support.CanMapValues[breeze.linalg.DenseVector[Double],Double,Nothing,breeze.linalg.DenseVector[Nothing]]
 required: breeze.linalg.support.CanMapValues[breeze.linalg.DenseVector[Double],Double,Double,breeze.linalg.DenseVector[Nothing]]
Note: Nothing <: Double, but trait CanMapValues is invariant in type B.
You may wish to define B as +B instead. (SLS 4.5)
              sin(DenseVector(3.0))
                 ^
<console>:22: error: could not find implicit value for parameter canSin: CanSin[breeze.linalg.DenseVector[Double],Output]
              sin(DenseVector(3.0))

Hrm… So, it turns out that what’s going on here is that Scala is looking at the first argument of the implicit params list (the CanMapValues one), and saying, what can I fill this with? It then decides that, at the moment, the third types (ToElement) is unconstrained, so it makes it Nothing, and chooses the CMV[DV[Double], Double, Nothing, DV[Nothing]] version of the implicit. (Simplifying a little…) Then, when it moves on, it can’t find a compatible choice for CanSin[Double, Nothing]. Rather than backtracking, it just gives up. Awesome.

If only we could make the type inference wait!

So, here—and often—it turns out that we can hold Scala’s hand a little and guide it through the search. What we want to do is make the Scala compiler hold off on deciding the type of ToElement and To until after it’s found an implicit for CanSin[Double, ???], for some type ???. To that end:

class HandHoldCMV[From, FromElement]

implicit def handHoldCMV_DV[T]:HandHoldCMV[DenseVector[T], T] =
     new HandHoldCMV[DenseVector[T], T]

Now, we just redefine the canSinMapValues implicit:

implicit def canSinMapValues[From, T, U, To]
         (implicit handHold: HandHoldCMV[From, T],
                   canSinT: CanSin[T, U],
                   cmv: CanMapValues[From, T, U, To]):CanSin[From, To] = ???

sin(DenseVector(1.0))

and it compiles! (At runtime, it throws an exception because we used ??? in place of a real implementation, but that’s just details.) So, in summary: Scala’s joint implicit selection/type inference algorithm proceeds greedily from left to right. It tries to find an implicit that matches an argument, and then fills it, inferring all types that that implicit parameter refers to. It then moves on to the next argument. If at any point one of its decisions was a bad one, it just throws up its hands and aborts.

It’d be nice if it were a full SAT solver or something, but compile times are bad enough already, so I guess I should be careful what I wish for.

Ok, I hope that’s helpful for someone besides me at some point. I feel like I understand what’s going on much better than I did.