本文
sealed class
を使ってトランポリン(Trampoline)を実装します。
sealed classとは
超簡単に言うと便利になった列挙型(enum
)です。
どう便利になったかというと、sealed class
を継承したクラスごとに状態や振る舞いを記述できるようになっています。
詳しい解説は以下の記事が参考になりました。
qiita.com
トランポリンとは
再帰を末尾再帰に書き直せるようにするデータ構造です。
トランポリンを用いることで、相互再帰のような、通常では末尾再帰に書き直せないコードも末尾再帰として書き表すことができます。
トランポリンそのものの動きを書くと長くなりそうだったので、sealed class
を使ってトランポリンを実装することだけを書きます。
動作の仕組みについては以下にまとめました。
qiita.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())
}