Itelable<T>のfoldとrunningFoldの違い

よくつかっているIterableの自作extensionを紹介します - Speaker Deck

で以下のようなコードを紹介した。

    fun <A, F, S> Iterable<T>.partitionMap(
        predicate: (A) -> Boolean,
        transformFirst: (A) -> F,
        transformSecond: (A) -> S
    ): Pair<List<F>, List<S>> = this.fold(Pair(emptyList(), emptyList())) { acc, it ->
        val (fList, sList) = acc
        if (predicate(it)) Pair(fList, sList.plus(transformSecond(it)))
        else Pair(fList.plus(transformFirst(it)), sList)
    }

に対して「runingFoldではなくfoldなのはなぜ?」という質問を頂いて、その場で答えられず「runningFoldを初めて聞いたのでわからないです。素人なので僕の引き出しではこれが限界でした」てきなやや礼節に欠く回答?態度?をしてしまったのでちゃんと調べておく。

foldとrunningFoldそれぞれの説明と実装はそれぞれ以下の通り。

まず fold
配列を走査して戻り値の型 R に変換していく。実装も単にforでぶん回してるだけなのでわかりやすい。

public inline fun <T, R> Iterable<T>.fold(initial: R, operation: (acc: R, T) -> R): R {
    var accumulator = initial
    for (element in this) accumulator = operation(accumulator, element)
    return accumulator
}

つぎに runningFold
引数はfoldと同様であるが、戻り値の型が List<R> になっている。foldとの違いは走査途中の operation の適用結果を溜めてリストに含めるという点か。 runningFold().last == fold() といえる。

public inline fun <T, R> Iterable<T>.runningFold(initial: R, operation: (acc: R, T) -> R): List<R> {
    val estimatedSize = collectionSizeOrDefault(9)
    if (estimatedSize == 0) return listOf(initial)
    val result = ArrayList<R>(estimatedSize + 1).apply { add(initial) }
    var accumulator = initial
    for (element in this) {
        accumulator = operation(accumulator, element)
        result.add(accumulator)
    }
    return result
}

runningFoldのシグネチャを見る限りとしては、やりたかった partitionMap は最終的に Pair<List<F>, List<S>> を返したいので、実装としてfold系統を使うならfoldが妥当そうである。

...
...
...

という話だけだとつまらないのとrunningFoldの使い所がわからなかったので、とくいげにrunningFoldのKEEP を読んでみる。言語仕様の背景を見るにはKEEPだと今日学んだので。
アルゴリズム的な目的で累積和を求めるのに使えるぞ的な説明が多め。アルゴリズム素人なので累積和って言葉自体が初めましてなのだが、配列の任意の区間の差とかを何度も取り出したい場合に一度累積和を出しておくと便利的なことらしい。

累積和 | アルゴリズムビジュアル大事典

ここまで調べてさすがに疲れたので寝る。
元気があったら追記する。