この記事はエムスリー 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 def
とimplicit 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!))
この場合は以下のように探索・解決されます。
implicitly[Box[Box[String]]]
に必要なBox[Box[String]]
の implicitな値を探すA = Box[String]
のとき、boxed
にマッチする- 2の
inner
に必要なBox[String]
のimplicitな値を探す A = String
のとき、boxed
にマッチする- 4の
inner
に必要なString
のimplicitな値を探す 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] {} }
Bob
がAlice
を好きなこと、また逆が成り立たないことをコンパイラが保証してくれます。切ないですね。
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以上であることを前提とする)
- 分子が0の場合
- (分子-分母)が割り切れる場合
さて、ここで(分子 - 分母)という引き算が出てきました。先ほど用意した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
割り切れる型
割り切れることを示す型を作りましょう。
// 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] {} }
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}" } }
優先順位をつける
これらは、以下の優先順位で解決してほしいので、継承関係を使ってこれを表現します。
- 3かつ5で割り切れる
- 3または5で割り切れる
- それ以外
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をかけるよ、というプログラミング猛者の方はぜひ弊社に遊びにきてください!