Path-dependent types in Scala

on waitingforcode.com

Path-dependent types in Scala

Before I went to Scala I had never imagined that we could do such many things nothing but with a types system. Aside of higher-kinded types or type boundaries that we can easily find in other languages, Scala offers more advanced type features as path-dependent types covered below.

This short post talks about type projection in Scala. The first part illustrates the situation when we can use it. The second part explains the concept itself and gives some example in its turn.

Inner classes

The behavior of path-dependent types relies strongly on inner classes. An inner class is the class included in another one that can't live without its parent. It means that the following code won't compile:

class Outer {
  class Inner
  def handleInner(inner: Inner) = {}
}
 
val inner = new Outer.Inner() 

Instead the inner class must be created alongside with its parent:

val outer = new Outer()
val inner = new outer.Inner()

That dependency also enforces another point - the instance of Inner used in Outer's method must be exactly the same as the one bounded to it. More concretely it means that the code below won't compile because of Error:(11, 22) type mismatch; found : Test.outer.Inner required: Test.outer2.Inner outer2.handleInner(inner) error:

val outer = new Outer()
val inner = new outer.Inner()
val outer2 = new Outer()
outer2.handleInner(

Inner classes and path-dependent types

The property of inner class can be used to build functions based on path-dependent types. To understand the concept, let's first see a problem it tries to solve:

describe("path-dependent types") {
  describe("when missing") {
    it("should show that we can mess up the computation") {
      def computeSum(numbersContainer: NumbersContainer)(numbersToAdd: NumbersContainer#Numbers): Int = {
        numbersToAdd.sum + numbersContainer.baseNumber
      }
      val container1 = new NumbersContainer(5)
      val numbers1 = new container1.Numbers(Seq(1, 2, 3))
      val container2 = new NumbersContainer(10)
      val numbers2 = new container2.Numbers(Seq(10, 20, 30))

      val sum = computeSum(container1)(numbers2)

      sum shouldEqual 65
    }
  }
}

The example shows a dangerous situation - our function computes the sum of 2 decorrelated objects. It's because the numbersToAdd argument is defined with type projection that accepts an instance of Numbers. To enforce the constraint between outer and inner classes, computeSum method should use path-dependent types:

describe("when defined") {
  it("should enforce function to process only elements of given instance") {
    def computeSum(numbersContainer: NumbersContainer)(numbersToAdd: numbersContainer.Numbers): Int = {
      numbersToAdd.sum + numbersContainer.baseNumber
    }
    val container1 = new NumbersContainer(5)
    val numbers1 = new container1.Numbers(Seq(1, 2, 3))
    val container2 = new NumbersContainer(10)
    val numbers2 = new container2.Numbers(Seq(10, 20, 30))

    val sum = computeSum(container1)(numbers1)

    sum shouldEqual 11

  }

We introduced a kind of type safety based on the values. The function accepts exclusively Numbers instance belonging to the same instance as NumbersContainer from the first parameter. Please notice that this example is a good candidate for DDD and implementing sum as a property of each Numbers inner class. It wasn't coded like that only for illustration purpose. The path-dependent types don't apply only to function arguments. They apply only to first-order types:

it("should allow to accumulate only instances belonging to given parent instance") {
  // In similar way that the previous example except that we want to store instances of a single parent and
  // compute their sum
  val numbersContainer = new NumbersContainer(3)
  val numbers = new mutable.ListBuffer[numbersContainer.Numbers]()
  (1 to 5).foreach(nr => {
    numbers.append(new numbersContainer.Numbers(Seq(nr)))
  })
  // And if we do:
  // val otherNumbersContainer = new NumbersContainer(4)
  // numbers.append(new otherNumbersContainer.Numbers(Seq(1, 2, 3)))
  // It won't compile because of:
  // Error:(54, 24) type mismatch;
  // found   : otherNumbersContainer.Numbers
  // required: numbersContainer.Numbers
  //        numbers.append(new otherNumbersContainer.Numbers(Seq(1, 2, 3)))

  val innerNumbersSum = numbers.map(innerNumbers => innerNumbers.sum).sum

  innerNumbersSum shouldEqual 15
}

And the counterexample of the same code but using type projection:

describe("type projection") {
  it("should not prevent about accumulating the inner classes of different parents") {
    // type projection is a way to enable to process the inner class instances of any parent
    val numbers = new mutable.ListBuffer[NumbersContainer#Numbers]()
    val numbersContainer = new NumbersContainer(3)
    val otherNumbersContainer = new NumbersContainer(4)
    numbers.append(new numbersContainer.Numbers(Seq(1, 2)))
    numbers.append(new otherNumbersContainer.Numbers(Seq(10, 11)))

    val innerNumbersSum = numbers.map(nr => nr.sum).sum

    innerNumbersSum shouldEqual 24
  }
}

Path-dependent types are very useful construct to enforce type safety by adding an extra level of safety from defined values. It prevents runtime bugs where accidentally mixed inner classes can lead to inconsistent results - exactly as in one of the first tests in the second section. The post also emphasized the difference with type projection that unlike path-dependent type doesn't carry about the specific instances.

Share, like or comment this post on Twitter:

Share on: