wrongwrongな開発日記

しんまいさんの忘備録

【プログラミング】sealed classでトランポリンを実装する【Kotlin】

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を用いてシールドクラス内に実装しています。