ScalaでAuxパターンをするときにはimplicitの順番に気をつけよう

はじめに

shapelessとかを使って型レベルプログラミングしてるとAuxパターンを使ってメソッドの型シグネチャで計算を表現することになる。
しかしこれが結構曲者でscalaのコンパイラの残念さもあり結構大変である。
その際に起こるコンパイルエラーの一つにimplicitの順番が関わるものがあるので紹介したい。

問題設定

一番カンタンな型レベル計算の題材として自然数の計算を扱おうと思う。
型レベル自然数は以下の様に定義できる。

trait Nat
trait Zero           extends Nat
trait Succ[P <: Nat] extends Nat

object Nat {
  type _0 = Zero
  type _1 = Succ[_0]
  type _2 = Succ[_1]
}

足し算は以下の様。

trait Sum[A <: Nat, B <: Nat] {
  type Out <: Nat
}

object Sum {
  type Aux[A <: Nat, B <: Nat, C <: Nat] = Sum[A, B] { type Out = C }

  implicit def sum1[B <: Nat]: Aux[_0, B, B] = new Sum[_0, B] { type Out = B }
  implicit def sum2[A <: Nat, B <: Nat, C <: Nat](implicit
    sum: Sum.Aux[A, Succ[B], C]
  ): Aux[Succ[A], B, C]                      = new Sum[Succ[A], B] { type Out = C }
}

引き算は以下の様。

trait Diff[A <: Nat, B <: Nat] {
 type Out <: Nat 
}

object Diff {
  def apply[A <: Nat, B <: Nat](implicit
    diff: Diff[A, B]
  ): Aux[A, B, diff.Out] = diff

  type Aux[A <: Nat, B <: Nat, C <: Nat] = Diff[A, B] { type Out = C }

  implicit def diff1[A <: Nat]: Aux[A, _0, A] = new Diff[A, _0] { type Out = A }
  implicit def diff2[A <: Nat, B <: Nat, C <: Nat](implicit
    diff: Diff.Aux[A, B, C]
  ): Aux[Succ[A], Succ[B], C]                 = new Diff[Succ[A], Succ[B]] { type Out = C }
}

型レベルの自然数を値に変換する型クラスも用意する。

trait ToInt[P <: Nat] {
  def apply(): Int
}

object ToInt {
  def apply[P <: Nat](implicit toInt: ToInt[P]): Int = toInt()

  implicit def zero: ToInt[_0] = new ToInt[Zero] {
    def apply(): Int = 0
  }

  implicit def succ[N <: Nat](implicit toInt: ToInt[N]): ToInt[Succ[N]] =
    new ToInt[Succ[N]] {
      def apply(): Int = toInt() + 1
    }
}

これらを使って少し複雑な計算を表現したい。
具体的には1を足して2を引く計算を表現しよう。
コードは以下の様になる。

case class Plus1AndMinus2[A <: Nat]() {
  def answer[B <: Nat, C <: Nat](implicit
    ev1: Sum.Aux[A, _1, B],
    ev2: Diff.Aux[B, _2, C],
    toInt: ToInt[C]
  ) = toInt()
}

これを使うと以下の様になる。

Plus1AndMinus2[_2].answer // => 1

2 + 1 – 2 = 1なので正しく動いている。

うまく動かないパターン

上で定義した計算のimplicitの順番を帰るとコンパイルが通らなくなる。

case class WrongPlus1AndMinus2[A <: Nat]() {
  def answer[B <: Nat, C <: Nat](implicit
    ev1: Diff.Aux[B, _2, C],
    ev2: Sum.Aux[A, _1, B],
    toInt: ToInt[C]
  ) = toInt()
}

WrongPlus1AndMinus2[_2].answer // could not find implicit value for parameter ev1: Diff.Aux[B,Nat._2,C]

これはおそらくだがコンパイラがimplicit引数を前から評価していき型を確定させていっているせいだと思われる。
そのため、間違っているパターンではBが確定しないためコンパイルが通らなくなるのだと考えられる。
正しいパターンではAと_1からBがまず確定し、確定したBと_2を使ってCが確定するという流れになるっぽい。

終わり

今回の例は比較的シンプルなものだが複雑な計算を組むとたまにこのミスをおかしてしまうので注意したい。