mike-neckのブログ

Java or Groovy or Swift or Golang

Kotlinの末尾再帰でFizzBuzz(Kotlin Advent Calendar 2016) #ktac2016

Kotlin

この記事はKotlin Advent Calendar2016の6日目の記事です。

昨日は RyotaMurohoshiさんの 「【!ってなんだ】KotlinとJava、nullとPlatformType【NullableにNotNull」 でした。

明日は kikuchy さんの 「」 です。

末尾再帰でFizzBuzz

この記事ではKotlinの末尾再帰を用いて、ややオーバーエンジニアリングなFizzBuzzのプログラムを書いていきます。 なお、この記事で用いたKotlinのバージョンは1.1-M02-8です。後のアップデートによっては動作しないことがありますが、ご了承ください。

FizzBuzzの型

まず、FizzBuzzの型を定義します。FizzBuzzの抽象的な型を Value とします。次の二点を考慮して Value を定義します。

  • Value は順列なので、次の値を持ちます。
  • Value は最終的に表示するので、文字列への変換を持ちます。

次に具体的な型を考えます。FizzBuzzの値として数値、Fizz/Buzz/FizzBuzz、 また順列の末端要素を用意します。

sealed class Value {
  abstract val show: String
  abstract val next: Value
}

object Term: Value() {
  override val show: String get() = throw UnsupportedOperationException("This is term")
  override val next: Value get() = throw UnsupportedOperationException("This is term")
}
class Num(val value: Int, override val next: Value): Value() {
  override val show: String = "$value "
}
class Fizz(override val next: Value): Value() {
  override val show: String = "Fizz "
}
class Buzz(override val next: Value): Value() {
  override val show: String = "Buzz "
}
class FizzBuzz(override val next: Value): Value() {
  override val show: String = "FizzBuzz\n"
}

FizzBuzz オブジェクト生成

定義した Value を生成していきますが、少しだけ考える必要があります。

単純に1から順番に Value にマッピングしていくと 1 -> 2 -> 3 の順番で Value(n) が作られます。 Value は次へのリンクを持ちますが、これは生成時にすでに存在している Value へのリンクになるため辿っていく順番は Value(3) -> Value(2) -> Value(1) の順番になります。 しかしFizzBuzzでは1から表示していきたいので、これでは不都合です。 Value(n) を作ったときにそのリンク先を一つ後の Value(n + 1) が設定されるようにするために、生成されたばかりの Value を引数にとって先頭の Value(つまり Value(1))を返す関数を作っていきます。また、その関数に Gen という別名を与えます。

typealias Gen = (Value) -> Value

val num: (Int) -> (Gen) -> Gen = { n -> { f -> { v -> f(Num(n, v)) } } }
val fizz:         (Gen) -> Gen =        { f -> { v -> f(Fizz(v)) } }
val buzz:         (Gen) -> Gen =        { f -> { v -> f(Buzz(v)) } }
val fizzBuzz:     (Gen) -> Gen =        { f -> { v -> f(FizzBuzz(v)) } }

なぜこんな面倒くさい関数を作っているかという点に関しては後ほど説明します。

カウント

3の倍数と5の倍数を調べるためのループカウンターを作ります。この型のプロパティには、同じ型で次のカウントを表す next を設定します。 次にこの型に 1 -> 2 -> 3 -> 1 -> ... とループするように最大値をもたせます。 この実装はループの途中を Mid 、ループの終端を End とします。

また、ループカウンターをそのまま末尾再帰関数の呼び出し回数を数えるのにも利用します。末尾再帰の呼び出し回数を数えるものについては Count という 別名を与えます。

interface Succ<L: Succ<L>> {
  val next: L
}

sealed class Loop: Succ<Loop> {
  abstract val max: Int
}

class Mid(val current: Int, override val max: Int): Loop() {
    override val next: Loop get() = if (current == max - 1) End(max) else Mid(current + 1, max)
}
class End(override val max: Int): Loop() {
    override val next: Loop get() = Mid(1, max)
}

typealias Count = Loop

関数用の補助

関数の補助をする関数を作ります。

関数 (P) -> Q と関数 (Q) -> R を合成する拡張関数 plus を (P) -> Q につけます。 また、引数をそのまま返す関数 id を作ります。

inline infix operator fun <P, Q, R> ((P) -> Q).plus(crossinline f: (Q) -> R): (P) -> R = { f(this(it)) }

fun <P> id(): (P) -> P = { it }

末尾再帰関数

ではFizzBuzzの列を構築していきます。

tailrec fun run(count: Count, three: Loop = Loop(3), five: Loop = Loop(5), result: Gen = id()): Value =
    when(count) {
      is End -> result(Term)
      is Mid -> when(five) {
        is End -> when(three) {
          is End -> run(count.next, three.next, five.next, fizzBuzz(result))
          is Mid -> run(count.next, three.next, five.next, buzz(result))
        }
        is Mid -> when(three) {
          is End -> run(count.next, three.next, five.next, fizz(result))
          is Mid -> run(count.next, three.next, five.next, num(count.current)(result))
        }
      }
    }

また Value を表示するための末尾再帰関数も作ります。

tailrec fun show(value: Value): Unit = when(value) {
  is Term -> Unit
  else    -> show(value.next.apply { print(value.show) })
}

生成した値をそのまま返すのではなく、関数にくるんで再び関数を適用していくやりかたを継続渡し(CPS)というらしいのですが、これを用いたところにKotlinで末尾再帰を書くときのコツがあります。関数ではなく、オブジェクトの順番に気をつけて Value をそのまま返すやり方を使ったらおそらくこのようになるでしょう。

tailrec fun run(count: Count, three: Loop = Loop(3), five: Loop = Loop(5)): Value =
// 中略
// Num だった場合
  is Mid -> Num(count.current, run(count.next, three.next, five.next))

しかし、このように定義した場合、関数 run は残念ながら末尾再帰になりません。

関数を末尾再帰にする場合、その関数は関数内部で一番最後に呼び出される関数にする必要があります。上記の場合であれば run 関数が呼ばれた後に Num コンストラクターが呼ばれており、再帰呼出しではあっても、末尾呼び出しではありません。このような場合、Kotlinコンパイラーは run を呼び出している箇所に「Recursive call is not a tail call」、 run 関数に「A function is marked tail-recursive but no tails call are found」と警告を出します。

そこでオブジェクトのリンクを作る処理を関数に閉じ込めて、再帰処理が終わった後に改めてその処理を実行するようにするため関数を作っていくようにしたわけです。

呼び出し

最終的に最大値(Int)からFizzBuzzの列(Value)を構築して、それを表示する関数(show)を呼び出して終わる(Unit)関数を作ります。

fun from1(max: Int): Count = Mid(1, max + 1)
val runApp: (Int) -> Unit = ::from1 + ::run + ::show

fun main(args: Array<String>): Unit = runApp(30)

Kotlinの末尾再帰によるFizzBuzzでした。末尾再帰は結果となる値を

  • 継続渡しスタイル(今回の関数)
  • 循環するデータにする(今回の Value のような構造)

ことがポイントです。

おわり