Kotlin
algorithm
再帰
末尾再帰
arrow-kt

【Kotlin】末尾再帰で10種類のアルゴリズムを実装する

この記事はMicroAd Advent Calendarの23日目の記事です。

続き

TL;DR

末尾再帰最適化を効かせてアルゴリズムを10種類実装します。
この記事で実装している内容+一部アルゴリズムのループによる実装+テストコードを以下に上げています。

前書き

先輩が書いたScalaではじめる末尾再帰に影響を受けたので、Kotlin + 末尾再帰で以下の10種類のアルゴリズムを実装してみました。

  1. 階乗
  2. ユークリッドの互除法
  3. フィボナッチ数
  4. 累乗(バイナリ法)
  5. 反復法(ニュートン法)
  6. 基数ソート
  7. 黄金比
  8. 偶奇判定
  9. マッカーシーの91関数
  10. アッカーマン関数

注意書き

面倒だったので本質的な部分にフォーカスするため、雑に実装しています。各実装に関する説明は脚注をご覧ください。

階乗/ユークリッドの互除法/フィボナッチ数

再帰といえば必ず出てくるアルゴリズムから3つを実装しました。

1. 階乗

fact
tailrec fun fact(n: BigInteger, ans: BigInteger = BigInteger.ONE): BigInteger {
    if(n.compareTo(BigInteger.ONE) < 1) return ans
    return fact(n.dec(), ans * n)
}

2. ユークリッドの互除法

gcd
tailrec fun gcd(a: Int, b: Int): Int{
    if(b == 0) return a
    return gcd(b, a%b)
}

3. フィボナッチ数1

fib
tailrec fun fib(n: BigInteger, a: BigInteger = BigInteger.ZERO, b: BigInteger = BigInteger.ONE): BigInteger{
    if(n == BigInteger.ONE) return a
    return fib(n.dec(), b, a+b)
}

累乗/反復法/基数ソート

ループで実装するような内容ですが、末尾再帰を用いて実装しました。
これらのアルゴリズムはループを使って実装すると状態管理が面倒ですが、末尾再帰で実装するとその辺りの管理が楽になります。

4. 累乗(バイナリ法)2

pow
tailrec fun pow(a: BigInteger, n: Int, ans: BigInteger = BigInteger.ONE): BigInteger{
    if(n == 0) return ans
    return pow(a * a,  n.ushr(1),  if(n.and(1) == 1) ans * a else ans)
}

5. 反復法(ニュートン法)3

newton
tailrec fun newton(
    f: (Double)-> Double,
    df: (Double)-> Double,
    x: Double,
    eps: Double = Float.MIN_VALUE.toDouble()
): Double {
    val xnew = x - f(x) / df(x)
    if(abs(xnew - x) < eps) return xnew
    return newton(f, df, xnew, eps)
}

汎化

反復法は$x_k$と漸化式(と閾値)があれば成り立つので、以下のような形に置き直すことができます。

iteration
tailrec fun iteration(
    r: (Double)-> Double,
    x: Double,
    eps: Double = Float.MIN_VALUE.toDouble()
): Double {
    val xnew = r(x)
    if(abs(xnew - x) < eps) return xnew
    return iteration(r, xnew, eps)
}

6. 基数ソート4

radixSort
tailrec fun radixSort(list: List<UInt>, mask: UInt = 1u): List<UInt> {
    if (mask == 0u) return list
    val small = ArrayList<UInt>()
    val big = ArrayList<UInt>()
    list.forEach {
        if(it and mask == 0u) small.add(it) else big.add(it)
    }
    small.addAll(big)
    return radixSort(small, mask.shl(1))
}

トランポリンを用いた末尾再帰最適化5

相互再帰や戻り値を使うような再帰などは通常末尾再帰最適化が効きませんが、トランポリンを用いることで末尾再帰として書くことができます。
トランポリンはArrowというライブラリのものを使用しています。

7. 黄金比6

goldenRatio
fun goldenRatio(n: Int): TrampolineF<Double> = when(n < 1){
    true -> Trampoline.done(1.0)
    else -> Trampoline.defer { goldenRatio(n-1) }.map{ 1.0 + (1/it) }
}

fun main(){ println(goldenRatio(10000).runT()) }

8. 偶奇判定

Even-Odd
fun odd(n: Int): TrampolineF<Boolean> = when (n) {
    0 -> Trampoline.done(false)
    else ->  Trampoline.defer { even(n - 1) }
}
fun even(n: Int): TrampolineF<Boolean> = when (n) {
    0 -> Trampoline.done(true)
    else -> Trampoline.defer { odd(n - 1) }
}

fun main(){
    println(even(10000).runT())
    println(odd(10000).runT())
}

9. マッカーシーの91関数7

mac
fun mc(n: Int): TrampolineF<Int> = when(n > 100){
    true -> Trampoline.done(n - 10)
    else -> Trampoline.defer { mc(n + 11) }.map{ mc(it).runT() }
}

fun main(){ println(mc(-1000000).runT()) }

10. アッカーマン関数

ack
fun ack(m: Int, n: Int): TrampolineF<Int> {
    if (m == 0) return Trampoline.done(n + 1)
    if (n == 0) return Trampoline.defer { ack(m-1, 1) }
    return Trampoline.defer { ack(m, n-1) }.map{ ack(m-1, it).runT() }
}

fun main(){ println(ack(3, 10).runT()) }

感想

実装を進めていくことで、そもそも言語仕様を深く把握しきれていなかったこと、関数型言語でよく使うような概念を把握できていないことなどに気づけたので、いい経験になったなと思います。
トランポリン関連の実装で用いたArrowは、書いている途中で存在を知ったため、動作の仕組みや実装について調べきることができませんでした。こちらも後で調査してみたいですね。


  1. この実装はn=1項目を0と置いて(=引数は1以上を想定して)います。 

  2. 自分のブログに解説記事を書いています。 

  3. この章は自分のブログを元に書いています。反復法の実用上は最大反復回数も書く必要がありますが、今回は飛ばしています。 

  4. 符号無し整数にのみ適用可能な実装です。 

  5. トランポリンとその使い方はこちらの記事を参考にさせていただきました。 

  6. 黄金比の計算はこちらの記事を参考にさせていただきました。 

  7. トランポリンを用いる場合、ものすごく再帰回数が多くなる(自分の環境では$n=-1000000000$とか)状態で実行するとjava.lang.OutOfMemoryError: Java heap spaceになります。