2018/12/22追記
ArrowというKotlinでの関数型プログラミングを支援するライブラリにトランポリンの実装が有りましたので、Arrowを使った方がいいです。
wrongwrong163377.hatenablog.com
本文
sealed class
を使ってトランポリン(Trampoline)を実装します。
sealed classとは
超簡単に言うと便利になった列挙型(enum
)です。
どう便利になったかというと、sealed class
を継承したクラスごとに状態や振る舞いを記述できるようになっています。
詳しい解説は以下の記事が参考になりました。
qiita.com
トランポリンとは
再帰を末尾再帰に書き直せるようにするデータ構造です。
トランポリンを用いることで、相互再帰のような、通常では末尾再帰に書き直せないコードも末尾再帰として書き表すことができます。
トランポリンそのものの動きを書くと長くなりそうだったので、sealed class
を使ってトランポリンを実装することだけを書きます。
動作の仕組みについては以下にまとめました。
qiita.com
末尾再帰について
末尾再帰については以下から続けて幾つか書いているので、よければ参考にしてください。
wrongwrong163377.hatenablog.com
sealed class部分を実装する
トランポリンでは「処理継続」と「処理終了」の2状態、加えてそれぞれの状態の値が必要となります。
「処理継続」の場合は処理として関数が、処理終了の場合は結果として定数が必要となります。
というわけで、sealed class
の実装は以下となります。
処理の継続をMore
が、処理の終了をDone
が表しており、値取り出し用にabstract
としてgetValue()
を実装しています。
//トランポリン sealed class Trampoline<T>{ //処理の継続 class More<T>(val calc: () -> Trampoline<T>): Trampoline<T>(){ override fun getValue(): T { return calc().getValue() } } //処理の終了 class Done<T>(private val value: T): Trampoline<T>() { override fun getValue(): T { return value } } //値取り出し用のインターフェース abstract fun getValue(): T }
トランポリン全体の実装
トランポリンを用いて末尾再帰を行うための関数2つを書きました。
本当はトランポリンのシールドクラス内にstatic関数として実装したかったのですが、Kotlin的にはパッケージレベル関数として記述するのが正しいようなので、外に出して実装しています*1。
前述したとおり、これの動きの解説は長くなるので別の機会にやるつもりです。
package trampoline //トランポリン sealed class Trampoline<T>{ //処理の継続 class More<T>(val calc: () -> Trampoline<T>): Trampoline<T>(){ override fun getValue(): T { return calc().getValue() } } //処理の終了 class Done<T>(private val value: T): Trampoline<T>() { override fun getValue(): T { return value } } //値取り出し用のインターフェース abstract fun getValue(): T } //トランポリンのランナー fun <T> run(func: () -> Trampoline<T>): T = run(func()).let { when (it) { is Trampoline.Done -> it.getValue() else -> throw Exception() } } //再帰処理本体 private tailrec fun <T> run(trampoline: Trampoline<T>): Trampoline<T> = when (trampoline) { is Trampoline.Done -> trampoline is Trampoline.More -> run(trampoline.calc()) }
参考にさせて頂いたコード
実装にあたってはこちらのコードを参考にさせて頂きました。
gist.github.com
*1:参考にさせて頂いたコードでは、companion objectを用いてシールドクラス内に実装しています。