エムスリーテックブログ

エムスリー(m3)のエンジニア・開発メンバーによる技術ブログです

ScalaのコンパイラにFizzBuzzを解いてもらう

この記事はエムスリー Advent Calendar 2018 かつ Scala Advent Calendar 2018の18日目の記事です。

エンジニアリンググループの冨岡です。

今回はどうしても自力では解けなかったFizzBuzz問題を、Scalaコンパイラの力を借りて解いた話をします。

FizzBuzzといえばコンピュータサイエンスの問題として広く親しまれている問題です。Wikipediaによると、コードが書けないプログラマ志願者を見分ける手法として提唱されているそうです。恐ろしいですね。

今回私は、Scalaコンパイラの力を借りてかろうじでFizzBuzzを解くことができたので、その方法を紹介します。ちょっとずるい気もしますが、依存ライブラリはなく、マクロも使っていないので許容範囲じゃないかと思います。

完成品はこちら

なお、今回Scalaのimplicitおよび型クラスを多用しています。馴染みのない方は@gakuzzzzさんによる「implicit入門」なども参考にしてみてください。

FizzBuzzの問題設定

FizzBuzzにはいろいろアレンジがありますが、今回の記事では以下をFizzBuzzの問題設定とします。

1~100までの各整数について、以下のルールで対応する文字列を出力する

- 3で割り切れる場合: Fizz
- 5で割り切れる場合: Buzz
- 3でも5でも割り切れる場合: FizzBuzz
- それ以外: 対象の整数

期待する出力の一部:
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...

難しそうですね。

方針と前提知識

Scalaコンパイラによるimplicitの探索・解決によってFizzBuzzが解かれるようにします。

implicit の探索・解決

Scalaのコンパイラは、implicitと指定したパラメータが明示的な値を与えられなかったときに、implicitの探索スコープにあるimplicitな変数、メソッドなどをコンパイル時に解決してくれます。

// 単純な例
implicit val i: String = "I am implicit"

// @inline def implicitly[T](implicit e: T) = e
// 探索スコープ内の型Tのimplicitな値を返す。(なければコンパイルエラー
println(implicitly[String]) // I am implicit

implicit defimplicit parameterの組み合わせで使うと、再帰的にimplicitな値を探索することも可能です。

// 再帰的な例
case class Box[A](a: A)
implicit val s: String = "I'm here!"
implicit def boxed[A](implicit inner: A): Box[A] = Box(inner)

println(implicitly[Box[Box[String]]]) // Box(Box(I'm here!))

この場合は以下のように探索・解決されます。

  1. implicitly[Box[Box[String]]] に必要な Box[Box[String]] の implicitな値を探す
  2. A = Box[String] のとき、 boxedにマッチする
  3. 2のinnerに必要なBox[String] のimplicitな値を探す
  4. A = String のとき、 boxed にマッチする
  5. 4のinnerに必要なStringのimplicitな値を探す
  6. sにマッチする

この際に解決される型パラメータや、implicit defを調整することによってScalaコンパイラの力を借りられそうです。

implicit探索スコープと優先順位

詳しく解説はしませんが、以下のポイントが重要です。

  • implicitな値が通常の変数スコープ内にない場合、関係ある型のcompanion objectも探索する
  • 継承などが行われている場合、base classの優先度が低い
  trait Priority
  case object Low extends Priority
  case object High extends Priority

  trait LowPriority {
    implicit val lowPriority: Priority = Low
  }
  object Priority extends LowPriority {
    implicit val highPriority: Priority = High
  }

  println(implicitly[Priority]) // High
implicitによる証明

implicitの探索・解決の仕組みを利用して、Scalaのコンパイラにある種の証明を行わせることができます。

  sealed trait Friend
  trait Bob extends Friend
  trait Alice extends Friend

  sealed trait Likes[A, B]
  object Likes {
    // Bob Likes Alice は Likes[Bob, Alice] と同じ意味
    implicit val bobLikesAlice: Bob Likes Alice =
      new Likes[Bob, Alice] {}
  }

f:id:jooohn:20181211013418p:plain
Bob Likes Aliceはimplicitな値が存在するのでコンパイルが通るが、Alice Likes Bob はそのようなimplicitな値がないためコンパイルエラーになる。

BobAliceを好きなこと、また逆が成り立たないことをコンパイラが保証してくれます。切ないですね。

1~100までの型を考える

今回の問題設定では、3や5,8という数を区別する必要があります。このような整数型は一般にInt,Longといった型で表現すると思いますが、いずれも一般的すぎてコンパイラの力を借りることができません

コンパイラに数を直接認識してもらえるように、各数ごとに型を用意してしまいましょう。

  sealed trait Nat
  trait Zero extends Nat

  // Natの次の数 をあらわす。 Successorが語源(多分)
  trait Succ[N <: Nat] extends Nat

  type Nat1  = Succ[Zero]
  type Nat2  = Succ[Nat1]
  type Nat3  = Succ[Nat2]
  type Nat4  = Succ[Nat3]
  type Nat5  = Succ[Nat4]

数0に相当するZero型を作りました。Succ[N <: Nat]はあるNat Nの次を意味します。 つまり、Succ[Zero]は"1"に相当する型、Succ[Succ[Zero]]は2を示す型となります。

type NatX は単なるaliasです。この調子で100まで作ってもいいのですが、5まであればまあ十分便利でしょう。それ以降のことはあとで考えます。

(macroを使うとより簡単になると思います。)

3でも5でも割り切れないときのために、一般的な数値型に変換する用意もしておきましょう。(デバッグ時にも役にたちます)

  // ToInt型クラス
  sealed trait ToInt[N <: Nat] { def value: Int }
  object ToInt {
    def apply[N <: Nat](implicit T: ToInt[N]): ToInt[N] = T

    // Zero の場合は 0
    implicit val zeroToInt: ToInt[Zero] = new ToInt[Zero] { def value: Int = 0 }

    // Succ[N]の場合は、(Nの数) + 1
    implicit def succToInt[N <: Nat](implicit T: ToInt[N]): ToInt[Succ[N]] =
      new ToInt[Succ[N]] { def value: Int = T.value + 1 }
  }
  println(ToInt[Zero].value) // 0
  println(ToInt[Nat3].value) // 3
  println(ToInt[Succ[Succ[Nat5]]].value) // 7

それっぽく動きそうです。

「割り切れる」ことを型で表現する

今作ったNat型を使って、割り切れることを型で表現してみましょう。 「割り切れる」ということの基本的な考え方を以下とします。(分母が1以上であることを前提とする)

  1. 分子が0の場合
  2. (分子-分母)が割り切れる場合

さて、ここで(分子 - 分母)という引き算が出てきました。先ほど用意したNatを用いてこれを型レベルで解けるようにしましょう。

型レベルの引き算
  // A - B のときの結果が Out
  sealed trait Diff[A <: Nat, B <: Nat] { type Out <: Nat }

  object Diff {
    def apply[A <: Nat, B <: Nat](implicit D: Diff[A, B]): Aux[A, B, D.Out] = D
    
    // この型エイリアスは型パズルを解くためのおまじないだと思ってください
    type Aux[A <: Nat, B <: Nat, C <: Nat] = Diff[A, B] { type Out = C }

    //  A - 0 の場合、その差分は A
    implicit def diffZero[A <: Nat]: Aux[A, Zero, A] = new Diff[A, Zero] { type Out = A }

    // (A + 1) - (B + 1) の結果は、 A - B と同じ
    implicit def diff[A <: Nat, B <: Nat, C <: Nat](implicit D: Aux[A, B, C]): Aux[Succ[A], Succ[B], C] = new Diff[Succ[A], Succ[B]] { type Out = C }
  }

これを用いてNatを用いた引き算らしきことができます。

  val diff = Diff[Nat5, Nat3]
  type Diff53 = diff.Out // Succ[Succ[Zero]]
  println(ToInt[Diff53].value) // 2

f:id:jooohn:20181211023009p:plain
負数になる場合はコンパイルエラーになる

割り切れる型

割り切れることを示す型を作りましょう。

  // N を D で割り切れる
  sealed trait Divisible[D <: Nat, N <: Nat]
  object Divisible {
    def apply[D <: Nat, N <: Nat](implicit D: Divisible[D, N]): Divisible[D, N] = D

    // Dが1以上のとき、0 は Dで割り切れる
    implicit def zeroDiv[D <: Succ[_]]: Divisible[D, Zero] = new Divisible[D, Zero] {}

    // Dが1以上のとき、(N - D) を D で割り切れるならば、NはDで割り切れる
    implicit def succDiv[D <: Succ[_], N <: Nat, Diff <: Nat](implicit diff: Diff.Aux[N, D, Diff], D: Divisible[D, Diff]): Divisible[D, N] =
      new Divisible[D, N] {}
  }

f:id:jooohn:20181211054117p:plain
割り切れる場合にのみimplicitな値が存在する

FizzBuzzの条件分岐

さて、型レベルで割り切れることが判定できるようになったので、FizzBuzzのキモでもある条件分岐と出力を実現していきます。

まずはインスタンス生成時になんらかの値を出力するFizzBuzz traitを宣言しておきます。

  sealed trait FizzBuzz[N <: Nat] {

    def out: String
    println(out)

  }
3 でも 5でも割り切れる

2つの条件をどちらも満たすことを要求する Andという型を作ってみましょう。

  sealed trait And[A, B]
  object And {
    implicit def and[A, B](implicit ev1: A, ev2: B): And[A ,B] = new And[A, B] {}
  }

これを用いて、15で割り切れる場合に"FizzBuzz"を紐づけたFizzBuzzインスタンスを解決するようにします。

  object FizzBuzz {

    def apply[N <: Nat](implicit F: FizzBuzz[N]): FizzBuzz[N] = F

    implicit def divisible3And5[N <: Nat](implicit A: Divisible[Nat3, N] And Divisible[Nat5, N]): FizzBuzz[N] =
      new FizzBuzz[N] { override def out: String = "FizzBuzz" }

  }
3で割り切れる場合にFizz, 5で割り切れる場合にBuzz

次に3または5で割り切れる場合も用意してみましょう。

  trait IfDivisible3Or5 {

    implicit def divisible3[N <: Nat](implicit D: Divisible[Nat3, N]): FizzBuzz[N] =
      new FizzBuzz[N] { override def out: String = "Fizz" }

    implicit def divisible5[N <: Nat](implicit D: Divisible[Nat5, N]): FizzBuzz[N] =
      new FizzBuzz[N] { override def out: String = "Buzz" }

  }
それ以外の場合

同様に、それ以外の場合も宣言します。

  trait OtherNat {
    implicit def otherwise[N <: Nat](implicit T: ToInt[N]): FizzBuzz[N] =
      new FizzBuzz[N] { override def out = s"${T.value}" }
  }
優先順位をつける

これらは、以下の優先順位で解決してほしいので、継承関係を使ってこれを表現します。

  1. 3かつ5で割り切れる
  2. 3または5で割り切れる
  3. それ以外
trait OtherNat
trait IfDivisible3Or5 extends OtherNat
object FizzBuzz extends IfDivisible3Or5

これで、あるNatに対応する文字列を出力できるようになりました。解決された順番で実行時に出力されます。

  FizzBuzz[Nat1]
  FizzBuzz[Nat3]
  FizzBuzz[Nat5]
  // 1
  // Fizz
  // Buzz

あと一歩です!

1~100までの数について対応する文字列を出力する

最後に、1~100までの数について実行する、いわゆるループ処理に相当する部分を書いていきます。

Nat100の型を得る

Nat1型は簡単です。

type Nat1 = Succ[Zero]

同様に Succ[Succ[Succ ... とSuccの入れ子を100回書けばいいわけですが、それはちょっと汚らしいですよね。macroを使えばうまく書けそうですが、今回はmacroをつかわずに数同士の計算から100の型を導き出してみます。

さきほどのDiffと同様に、加算を担うSumと乗算を担うProdを定義します。発想はDiffとほぼ同じなので省略します。

  val nat10 = Prod[Nat2, Nat5]
  type Nat10 = nat10.Out
  println(ToInt[Nat10].value) // 10

  val nat100 = Prod[Nat10, Nat10]
  type Nat100 = nat100.Out
  println(ToInt[Nat100].value) // 100

Nat100を定義することができました。

繰り返しの処理

これもコンパイラにやってもらいたいものです。あるNat範囲に関してimplicit parameterの解決をするRangeという型を用意してみましょう。

  sealed trait Range[E[_ <: Nat], A <: Nat, B <: Nat]
  object Range {

    def apply[E[_ <: Nat], A <: Nat, B <: Nat](implicit R: Range[E, A, B]): Range[E, A, B] = R

    // A = B = N のときは E[N]を解決する
    implicit def equal[E[_ <: Nat], N <: Nat](implicit E: E[N]): Range[E, N, N] = new Range[E, N, N] {}

    // Range[E, A, B] が解決できるなら、 E[Succ[B]] を解決する
    implicit def range[E[_ <: Nat], A <: Nat, B <: Nat](implicit R: Range[E, A, B], E: E[Succ[B]]): Range[E, A, Succ[B]] = new Range[E, A, Succ[B]] {}
  }

これにより、例えばRange[FizzBuzz, Nat1, Nat3]のimplicit parameterの部分を、コンパイラが以下のように解決してくれます。

  Range[FizzBuzz, Nat1, Nat3](
    Range.range(
      R = Range.range(
        R = Range.equal(
          FizzBuzz[Nat1]
        ),
        E = FizzBuzz[Nat2]
      ),
      E = FizzBuzz[Nat3]
    )
  )

FizzBuzz[Nat1], FizzBuzz[Nat2], FizzBuzz[Nat3]が順番に展開されるのがわかりますね。

完成!

  Range[FizzBuzz, Nat1, Nat100]

これが評価されたときに問題のFizzBuzz出力を行うようになりました。

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
...

ちなみにコンパイルにはめちゃめちゃ時間がかかります。

まとめ

Scalaコンパイラの力を借りてなんとかFizzBuzzを解くことができました!これでコードが書けないと言われずにすみそうです。

FizzBuzzをかけるエンジニア募集中

私には難しすぎて断念しましたが、Scalaのimplicit探索の力を借りずに、実行時のif式やfor式だけでエレガントにFizzBuzzをかけるよ、というプログラミング猛者の方はぜひ弊社に遊びにきてください!

jobs.m3.com

参考