この記事はMicroAd Advent Calendarの23日目の記事です。
続き
TL;DR
末尾再帰最適化を効かせてアルゴリズムを10種類実装します。
この記事で実装している内容＋一部アルゴリズムのループによる実装＋テストコードを以下に上げています。
前書き
先輩が書いたScalaではじめる末尾再帰に影響を受けたので、Kotlin + 末尾再帰で以下の10種類のアルゴリズムを実装してみました。
- 階乗
- ユークリッドの互除法
- フィボナッチ数
- 累乗（バイナリ法）
- 反復法（ニュートン法）
- 基数ソート
- 黄金比
- 偶奇判定
- マッカーシーの91関数
- アッカーマン関数
注意書き
面倒だったので本質的な部分にフォーカスするため、雑に実装しています。各実装に関する説明は脚注をご覧ください。
階乗/ユークリッドの互除法/フィボナッチ数
再帰といえば必ず出てくるアルゴリズムから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は、書いている途中で存在を知ったため、動作の仕組みや実装について調べきることができませんでした。こちらも後で調査してみたいですね。