Typelevel FizzBuzz in Scala

Scalaの型レベルプログラミングをFizzBuzzにより解説します。

型レベルプログラミング

型で計算を行う手法のことで、以下の利点があります。

自然数の定義

自然数はZeroSuccにより帰納的に定義できます。

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

0から15までの自然数はNatを使って以下のように表すことができます。

type _0 = Zero
type _1 = Succ[_0]
type _2 = Succ[_1]
type _3 = Succ[_2]
type _4 = Succ[_3]
type _5 = Succ[_4]
type _6 = Succ[_5]
type _7 = Succ[_6]
type _8 = Succ[_7]
type _9 = Succ[_8]
type _10 = Succ[_9]
type _11 = Succ[_10]
type _12 = Succ[_11]
type _13 = Succ[_12]
type _14 = Succ[_13]
type _15 = Succ[_14]

ここで、型レベルの自然数Natを値Intへ変換することを考えましょう。

ToIntは自然数Nに対しIntを対応させます。

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

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

ToInt.applyは自然数Nにより決定されるToIntのインスタンスのapplyメソッドを呼び出しています。

ToIntのインスタンスは次のように定義できます。

implicit def zero: ToInt[Zero] =
  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
  }

ToInt[Zero]は0を返します。

ToInt[Succ[N]]ToInt[N]に1加えた値を返します。

ToIntは次のように動作します。

assert(ToInt[_0] == 0)
assert(ToInt[_9] == 9)

演算の定義

FizzBuzzを計算する為にはNatに対して剰余を定義する必要があります。

剰余の定義の為に四則演算を定義しましょう。

trait Plus[N <: Nat, M <: Nat] {
  type Result <: Nat
}

trait Minus[N <: Nat, M <: Nat] {
  type Result <: Nat
}

trait Mult[N <: Nat, M <: Nat] {
  type Result <: Nat
}

trait Div[N <: Nat, M <: Nat] {
  type Result <: Nat
}

四則演算は自然数N, Mに対して計算結果Resultを対応させます。

Divの定義の為にLTを定義します。

trait LT[N <: Nat, M <: Nat]

LTのインスタンスは次のように定義できます。

object LT {
  implicit def zero[N <: Nat]: LT[Zero, Succ[N]] = new LT[Zero, Succ[N]] {}
  implicit def succ[N <: Nat, M <: Nat](implicit lt: LT[N, M]): LT[Succ[N], Succ[M]] = new LT[Succ[N], Succ[M]] {}
}

Zero < Succ[N]は真です。

N < MならばSucc[N] < Succ[M]は真です。

LTの動作は次のように確認できます。

implicitly[LT[_2, _3]]
implicitly[LT[_3, _6]]

Plusのインスタンスは次のように定義できます。

object Plus {
  implicit def zero[N <: Nat]: Plus[N, Zero] { type Result = N } =
    new Plus[N, Zero] {
      type Result = N
    }
  implicit def succ[N <: Nat, M <: Nat](implicit plus: Plus[N, M]): Plus[N, Succ[M]] { type Result = Succ[plus.Result] } =
    new Plus[N, Succ[M]] {
      type Result = Succ[plus.Result]
    }
}

N + ZeroNを結果とします。

N + MRを結果とするならばN + Succ[M]Succ[R]を結果とします。

Plusの動作は次のように確認できます。

implicitly[Plus[_2, _3] { type Result = _5 }]
implicitly[Plus[_6, _9] { type Result = _15 }]

Minusのインスタンスは次のように定義できます。

object Minus {
  implicit def zero[N <: Nat]: Minus[N, Zero] { type Result = N } =
    new Minus[N, Zero] {
      type Result = N
    }
  implicit def succ[N <: Nat, M <: Nat](implicit minus: Minus[N, M]): Minus[Succ[N], Succ[M]] { type Result = minus.Result } =
    new Minus[Succ[N], Succ[M]] {
      type Result = minus.Result
    }
}

N - ZeroNを結果とします。

N - MRを結果とするならばSucc[N] - Succ[M]Rを結果とします。

Minusの動作は次のように確認できます。

implicitly[Minus[_6, _4] { type Result = _2 }]
implicitly[Minus[_9, _6] { type Result = _3 }]

Multのインスタンスは次のように定義できます。

object Mult {
  implicit def zero[N <: Nat]: Mult[N, Zero] { type Result = Zero } =
    new Mult[N, Zero] {
      type Result = Zero
    }
  implicit def one[N <: Nat]: Mult[N, Succ[Zero]] { type Result = N } =
    new Mult[N, Succ[Zero]] {
      type Result = N
    }
  implicit def succ[N <: Nat, M <: Nat, R <: Nat](implicit mult: Mult[N, Succ[M]] { type Result = R }, plus: Plus[N, R]): Mult[N, Succ[Succ[M]]] { type Result = plus.Result } =
    new Mult[N, Succ[Succ[M]]] {
      type Result = plus.Result
    }
}

N * ZeroZeroを結果とします。

N * Succ[Zero]Nを結果とします。

N * MRを結果とするならばN * Succ[M]N + Rを結果とします。

Multの動作は次のように確認できます。

implicitly[Mult[_2, _0] { type Result = _0 }]
implicitly[Mult[_3, _2] { type Result = _6 }]

Divのインスタンスは次のように定義できます。

object Div {
  implicit def zero[N <: Nat, M <: Nat](implicit lt: LT[N, M]): Div[N, M] { type Result = Zero } =
    new Div[N, M] {
      type Result = Zero
    }
  implicit def succ[N <: Nat, M <: Nat, R <: Nat](implicit minus: Minus[N, M] { type Result = R }, div: Div[R, M]): Div[N, M] { type Result = Succ[div.Result] } =
    new Div[N, M] {
      type Result = Succ[div.Result]
    }
}

N < MならばZeroを結果とします。

N - MRを結果とするならばN / MSucc[R / M]を結果とします。

Divの動作は次のように確認できます。

implicitly[Div[_6, _4] { type Result = _1 }]
implicitly[Div[_9, _3] { type Result = _3 }]

この四則演算を使って剰余は次のように定義できます。

trait Mod[N <: Nat, M <: Nat] {
  type Result <: Nat
}

object Mod {
  implicit def mod[N <: Nat, M <: Nat, Q <: Nat, R <: Nat](implicit div: Div[N, M] { type Result = Q }, mult: Mult[Q, M] { type Result = R }, minus: Minus[N, R]): Mod[N, M] { type Result = minus.Result } =
    new Mod[N, M] {
      type Result = minus.Result
    }
}

(N / M) * Mの結果がRならばN mod MN - Rを結果とします。

Modの動作は次のように確認できます。

implicitly[Mod[_3, _2] { type Result = _1 }]
implicitly[Mod[_8, _3] { type Result = _2 }]
implicitly[Mod[_1, _3] { type Result = _1 }]

FizzBuzz

FizzBuzzは次のように定義します。

trait FizzBuzz[N <: Nat] {
  def apply(): String
}

object FizzBuzz {
  def apply[N <: Nat](implicit lt: LT[_0, N], fizzbuzz: FizzBuzz[N]): String = fizzbuzz()
}

FizzBuzzは自然数Nに対応するStringの値を持ちます。

FizzBuzzのインスタンスは次のように定義できます。

implicit def fizzbuzz[N <: Nat](implicit mod: Mod[N, _15] { type Result = _0 }): FizzBuzz[N] =
  new FizzBuzz[N] {
    def apply(): String = "FizzBuzz"
  }

ここで"Fizz""Buzz"に対するインスタンスを定義すると、"FizzBuzz"に対するのインスタンスとの間でコンフリクトが発生します。

そこで、implicit parameterの解決の為に階層を構築します。

trait FizzBuzzLowestPriorityImplicits {
  implicit def number[N <: Nat](implicit toInt: ToInt[N]): FizzBuzz[N] =
    new FizzBuzz[N] {
      def apply(): String = toInt().toString
    }
}

trait FizzBuzzLowerPriorityImplicits extends FizzBuzzLowestPriorityImplicits {
  implicit def fizz[N <: Nat](implicit mod: Mod[N, _3] { type Result = _0 }): FizzBuzz[N] =
    new FizzBuzz[N] {
      def apply(): String = "Fizz"
    }
  implicit def buzz[N <: Nat](implicit mod: Mod[N, _5] { type Result = _0 }): FizzBuzz[N] =
    new FizzBuzz[N] {
      def apply(): String = "Buzz"
    }
}

object FizzBuzz extends FizzBuzzLowerPriorityImplicits {
  implicit def fizzbuzz[N <: Nat](implicit mod: Mod[N, _15] { type Result = _0 }): FizzBuzz[N] =
    new FizzBuzz[N] {
      def apply(): String = "FizzBuzz"
    }
}

この定義により、FizzBuzzからFizzBuzzLowerPriorityImplicits, FizzBuzzLowestPriorityImplicitsの順にimplicitが解決されます。

FizzBuzzは次のように動作する。

assert(FizzBuzz[_2] == "2")
assert(FizzBuzz[_3] == "Fizz")
assert(FizzBuzz[_5] == "Buzz")
assert(FizzBuzz[_15] == "FizzBuzz")

これで型レベルFizzBuzzは完成です。