Functional dependencies are a near-standard extension to Haskell (present in GHC and elsewhere) which allow constraints on the type parameters of type classes to be expressed and then enforced by the compiler. They allow the programmer to state that some of the type parameters of a multi-parameter type class are completely determined by the others. One particularly common application of this is allowing the result type of a function to be a parameter but nevertheless determined by the type(s) of it’s argument(s) — the examples on the Haskell wiki page that I linked to above illustrate that extremely well.

Does this have an equivalent in Scala? We certainly have the equivalent problem — whenever we have multiple type parameters (of a type or method) we might want to be able to express functional dependency-like constraints between those type parameters and have those constraints checked by the compiler. And ideally we want that to get along well with type-inference — we would like the compiler to be able to infer any types which are determined by types which it is already able to infer.

It turns out that there’s a very simple translation of Haskell-style functional dependencies to Scala, but for some reason this doesn’t seem to have been commented on. Quite the opposite in fact — I’ve seen it reported that encoding fundeps in Scala is either impossible, or possible but not useful because of issues with type inference. What makes this even more surprising is that a crucial feature of Scala’s (now not so) new collections framework (CanBuildFrom) appears to be a perfect example of this encoding in practice … strangely this isn’t advertised in Type Classes as Objects and Implicits (Olivera, Odersky and Moors, 2010) either.

Maybe this has all been noticed before and assumed to be too obvious to mention, nevertheless, I think it’s useful to be able to make the connection. I’ll illustrate the translation using the examples from the Haskell wiki. By the time I’m done translating them into Scala the fact that CanBuildFrom is an instance of a fundep should be quite clear.

Let’s start with the matrix/vector/scalar multiplication example. Here we want to express the fact that the result type of the multiplication is fully determined by it’s arguments,

        Matrix * Matrix => Matrix
        Matrix * Vector => Vector
        Matrix * Int    => Matrix
           Int * Matrix => Matrix

Here we have a triple of types where the first two (the argument types) determine the third (the result type). Lets express this relationship directly via a trait with three type parameters accompanied by some implicit definitions which capture the relationship we want to enforce,

trait Matrix // Dummy definitions for expository purposes
trait Vector

trait MultDep[A, B, C]
  
implicit object mmm extends MultDep[Matrix, Matrix, Matrix]
implicit object mvv extends MultDep[Matrix, Vector, Vector]
implicit object mim extends MultDep[Matrix, Int, Matrix]
implicit object imm extends MultDep[Int, Matrix, Matrix]

Given these definitions we can ask the compiler what is and what isn’t allowed,

// OK: Matrix * Matrix -> Matrix
scala> implicitly[MultDep[Matrix, Matrix, Matrix]]
res0: MultDep[Matrix,Matrix,Matrix] = mmm$@1ddeda2

// OK: Matrix * Vector -> Vector
scala> implicitly[MultDep[Matrix, Vector, Vector]]
res1: MultDep[Matrix,Vector,Vector] = mvv$@1a8fb1b

// Error
scala> implicitly[MultDep[Matrix, Vector, Matrix]]
<console>:15: error: could not find implicit value for 
  parameter e: MultDep[Matrix,Vector,Matrix]

The first two cases are fine, because they both correspond to one of the implicit instances we provided earlier. The third fails, quite rightly, because there is no instance corresponding to Matrix * Vector -> Matrix.

So, we’ve been able to capture the desired relationship between the type variables. Here’s how we put that to use,

def mult[A, B, C](a: A, b: B)
  (implicit instance: MultDep[A, B, C]): C =
    error("TODO")

// Type annotations solely to verify that the correct result type
// has been inferred

val r1: Matrix = mult(new Matrix {}, new Matrix{}) // Compiles
val r2: Vector = mult(new Matrix {}, new Vector{}) // Compiles
val r3: Matrix = mult(new Matrix {}, 2)            // Compiles
val r4: Matrix = mult(2, new Matrix {})            // Compiles

// This next one doesn't compile ...
val r5: Matrix = mult(new Matrix {}, new Vector{}) 

Notice how the third type parameter, C, isn’t used in the first (explicit) parameter list. If it weren’t for its appearance in the second (implicit) parameter list the compiler would normally infer it as Nothing — not what we want at all. But the combination of type inference and implicit search saves the day. The first two type parameters A and B are inferred from the explicit arguments to mult(), then implicit search kicks in, attempting to locate an implicit definition of MultDep[_, _, _] consistent with those two types. By construction, it will only ever find one, and that is sufficient to uniquely determine C for use as the result type of the function.

We have the signature of our mult() function sorted out, now for the implementation. The (hopefully fairly obvious) trick here is to make our MultDep instances provide the implementations of the different cases as well as the type constraints,

implicit object mmm extends MultDep[Matrix, Matrix, Matrix] {
  def apply(m1: Matrix, m2: Matrix): Matrix = error("TODO")
}

implicit object mvv extends MultDep[Matrix, Vector, Vector] {
  def apply(m1: Matrix, v2: Vector): Vector = error("TODO")
}

implicit object mim extends MultDep[Matrix, Int, Matrix] {
  def apply(m1: Matrix, i2: Int): Matrix = error("TODO")
}

implicit object imm extends MultDep[Int, Matrix, Matrix] {
  def apply(i1: Int, m2: Matrix): Matrix = error("TODO")
}

(filling out the bodies of the dummy apply() methods is an exercise left for the reader). We can now complete the definition of mult(),

def mult[A, B, C](a: A, b: B)
  (implicit instance: MultDep[A, B, C]): C = 
    instance(a, b)

And that’s all there is to it. The implicit objects correspond exactly to the type class instances in the Haskell original, and the combination of type inference and implicit search captures the functional dependency directly.

Here’s the second example from Haskell wiki page, translated in the same way,

trait ExtractDep[A, B] {
  def apply(a: A): B
}
  
implicit def ep[A, B] = new ExtractDep[(A, B), A] {
  def apply(p: (A, B)): A = p._1
}
  
def extract[A, B](a: A)
  (implicit instance: ExtractDep[A, B]): B = instance(a)

// Type annotation solely to verify that the correct result type
// has been inferred
val c: Char = extract(('x', 3))

Of course, neither of these two examples are particularly exciting in Scala as they stand — Scala has Java-style overloading, which makes the matrix/vector/scalar example mostly redundant; and the second example is a little too artificial to be compelling. Nevertheless, there are many situations where being able to express similar constraints amongst type parameters can be extremely useful — Scala embedded DSLs often have to deal with situations which are equivalent to wanting a function result type to be determined by its argument types, and I know of a number of DSL designers who’ve struggled with the problem of Nothing being inferred unhelpfully for unconstrained result types.

But the best widely known example of a fundep is right under our noses in the Scala standard library itself: CanBuildFrom. Let’s take a look at (a slight simplification of) of the part of its definition which expresses type constraints,

trait CanBuildFrom[From, Elem, To] {
  def apply ...
}

Instances of this trait capture collection-type-specific constraints on whether or not a collection of type To with elements of type Elem can be created from a collection of type From. For “regular” collection types (collections which can hold elements of any type) the corresponding instance is equivalent to,

implicit def regularCanBuildFrom[CC[_], A] =
  new CanBuildFrom[CC[_], A, CC[A]] {
    def apply ...
  }

In effect this asserts that for a regular collection type it’s possible to create a new collection of the same shape, but with an arbitrarily substituted element type. We can ask the compiler about these relationships like so,

scala> import scala.collection.generic._
import scala.collection.generic._

scala> implicitly[CanBuildFrom[List[Int], String, List[String]]]
res0: CanBuildFrom[List[Int],String,List[String]] = ...

scala> implicitly[CanBuildFrom[Set[String], Double, Set[Double]]]
res1: CanBuildFrom[Set[String],Double,Set[Double]] = ...

// These two don't compile ...
scala> implicitly[CanBuildFrom[List[String], Int, List[Double]]]
<console>:11: error: ...

scala> implicitly[CanBuildFrom[List[String], Int, Set[Int]]]
<console>:11: error: ...

As you can see from these examples, the third type argument in CanBuildFrom is determined by its first two — it takes its type constructor from the first type argument and its element type from the second type argument. Any attempt to deviate from that pattern results in a static compile time error. This should be sounding familiar …

Now lets look at where this abstraction is used: the definition of TraversibleLike.map(),

def map[B, That](f: A => B)
  (implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    b.sizeHint(this) 
    for (x <- this) b += f(x)
    b.result
  }

It should be apparent that here, like the matrix/vector/scalar example, we have a method with a parametrized result type which is not used in any of its explicit argument types, and hence which can’t be inferred from its explicit arguments. Just as in the earlier case, it’s the implicit argument which is determining the otherwise unconstrained result type via implicit search for a CanBuildFrom instance with type parameters B (determined by type inference from the explicit parameter list) and Repr (effectively a constant). It should also be apparent that the implicit argument is providing a significant component of the implementation of this method via the call bf(repr) — this is exactly analogous to the calls of instance(a, b) in the earlier example.

Hopefully the discussion above will have persuaded you that these are the hallmarks of a Haskell-like functional dependency, right at the heart of the Scala collections framework. And in my book, that makes fundeps in Scala neither impossible nor useless.

trait MultDep[-A, -B, C] extends Function2[A, B, C]

class ... {
  def mult(a: Matrix, b: Matrix): Matrix = ...
  def mult(a: Matrix, b: Vector): Vector = ...
  def mult(a: Matrix, b: Int): Matrix = ...
  def mult(a: Int, b: Matrix): Matrix = ...
}

trait ExtractDep[A] {
  type B
  def apply(a : A) : B
}

implicit def ep[P, Q] = new ExtractDep[(P, Q)] {
  type B = P
  def apply(p : (P, Q)) : P = p._1
}

// etc