【Kotlin】generateSequenceを使って反復法を実装する #Kotlin

この記事で使っていたリポジトリはこちら。

TL;DR

数値解析などで使う反復法はgenerateSequenceを使って実装すると書きやすい
実装例
- ニュートン法
- 二分法
ただしKotlinのtakeWhileでは扱いが厳しい場面が有るので、自分が作ったtakeFor使ってください

実装

まず実装例を紹介します。
ただし、冒頭や前回の記事で触れたとおり、takeWhileでは収束条件を満たした解が得られないため、この記事では前回の記事で作ったtakeForを使っています。

`iterationSequence`

ニュートン法のような、単純な反復法を回すための関数です。
generateSequenceのseedにはnullとx0を指定していますが、この関数ではxとxNewの比較をする必要が有り、かつ最初のxが定められないためです。
その他詳細はコメントに記載しました。

iterationSequence

//反復法
fun<T : Any> iterationSequence(
    f: (T) -> T, //漸化式
    x0: T, //初期値
    cond: (T, T) -> Boolean, //収束条件
    nMax: Int = 10000 //反復回数上限
): List<T> = generateSequence( Pair<T?, T>(null, x0)) { (_, xNew) ->
    xNew to f(xNew)  //xの更新
}.takeFor { (x, xNew) ->
    if(x == null) true else !cond(x, xNew) //収束判定、xは初期値nullなのでnull回避が必要
}.map {
    it.second //Pairから配列へ変換
}.take(nMax).toList() //nMaxまで行ったら終了、Listにして返却

処理の順序は以下の通りです。

generateSequenceで、fを用いてxを更新し続ける無限シークエンスを宣言
takeForで、収束条件を満たす所までにシークエンスを制限
Pairのシークエンスから、mapでit.second（つまりx0から終端まで）のシークエンスに変換
takeで最大反復回数までにシークエンスを制限し、toList()でリストにして返却

`binaryIterationSequence`

二分法を回すための関数です。
二分法では更新に用いた値を保持する必要が有るため、区間を表すa, bにcを加えたTripleをseedに指定しています。
その他詳細はコメントに記載しました。

binaryIterationSequence

//二分法の中点計算用
fun calcHalf(a: Double, b: Double): Double = (a + b) / 2.0
//二分法
fun binaryIterationSequence(
    f: (Double) -> Double, //入力関数
    trueValue: Double, //二分法の真値
    a0: Double, //小さい方の初期値
    b0: Double, //大きい方の初期値
    nMax: Int = 10000 //反復回数上限
): List<Double> = generateSequence(Triple(a0, b0, calcHalf(a0, b0))) { (a, b, c) ->
    when { //更新
        f(a) * f(c) > 0.0 -> Triple(c, b, calcHalf(c, b))
        f(b) * f(c) > 0.0 -> Triple(a, c,  calcHalf(a, c))
        else -> throw RuntimeException("条件判定に失敗しました")
    }
}.map {
    it.third //TripleのシークエンスからDoubleのシークエンスに変換
}.takeFor {
    abs(f(it) - trueValue) >= 1.0E-15 //収束判定
}.take(nMax).toList() //nMaxまで行ったら終了、Listにして返却

処理の順序は以下の通りです。

二分法で検証区間とcを更新し続ける無限シークエンスを宣言
Tripleのシークエンスから、mapでcのシークエンスに変換
takeForで、収束条件を満たす所までにシークエンスを制限
takeで最大反復回数までにシークエンスを制限し、toList()でリストにして返却

使う

上記2つの関数のテストコードです。

SequenceTest

import org.junit.jupiter.api.Assertions
import org.junit.jupiter.api.Test
import kotlin.math.PI

class SequenceTest{
    @Test //netwon法でx^3-2=0となるxを計算
    fun testIterationSequence(){
        val ans = iterationSequence(::newtonF, 1.0, ::condDouble)
        val last = ans.last()
        Assertions.assertTrue(10000 > ans.size)
        Assertions.assertEquals(2.0, last * last * last, Float.MIN_VALUE.toDouble())
    }

    @Test //二分法でsin(x/4) - cos(x/4) = 0（つまりx = pi）となるxを計算
    fun testBinarySequence(){
        val ans = binaryIterationSequence(::binaryF, 0.0, 0.0, 5.0)
        Assertions.assertTrue(10000 > ans.size)
        Assertions.assertEquals(PI, ans.last(), 1.0E-15)
    }
}

どう書きやすいのか

反復法の書きにくさ

反復法は、愚直にループを使って実装すると以下のような書きにくさが有ります。

状態などを保持するため、ミュータブルな変数が増える
- 可読性を損なう
- バグの温床になる
停止条件が複雑になるため判定が面倒
- 実用的には収束条件+最大ループ回数の判定が必要

末尾再帰を使うとどうか？

以前の記事で「末尾再帰を使うと反復法が書きやすい」という旨を主張しました。
簡単に書くだけであれば末尾再帰で書いた方が書きやすいと思いますが、末尾再起では更新の必要が無い変数も関数に渡していく必要が有るため、その部分は冗長になってしまいます。
特にこの記事の例のようなある程度現実的なコードでは、判定するものが増えるたびに引数もどんどん増えていくので、generateSequenceを使った方が簡潔に書くことができます。

`generateSequence`を使うことによる書きやすさ

単純ループ、末尾再起による書き方と比較して、generateSequenceを使うことで以下のような書きやすさが得られます。

状態保持のための変数が必要なくなり、状態を全てイミュータブルに管理できる
- 簡潔かつバグを少なく書くことができる
終了条件の判定が楽に書ける

この辺りはiterationSequenceやbinaryIterationSequenceにvarどころかvalすら登場しない辺りで効果が見られると思います。

`generateSequence`を使うことによる書きにくさ

慣れないと読みにくいことと、このパターンではKotlinに素で用意されているtakeWhileが使いにくいことでしょうか。
近年マルチパラダイム言語が流行っているので、前者は習得する積極的な理由が有ると思いますが、後者はちょっと厳しさが有りますね……。
書いてみてから例が悪かったかなと反省していますが、とりあえずSequence関連は便利なので使っていった方がいいと思います。

【Kotlin】generateSequenceを使って反復法を実装する