kotlin - 在 Kotlin 中以纯函数式编程风格在 O(n) 时间内计算所有前缀和

Question

是否可以计算purely functional programming中的数字数组的所有前缀和Kotlin 中的 O(n) 时间风格？

我所说的纯函数式编程是指仅允许对集合使用函数式编程扩展函数，例如 map、reduce、fold、 _Collections,kt 中的 sum 等，而传统的命令式编程方法涉及改变状态和可变数据，例如普通循环、可变变量(又名var)和可变数组，这是不允许的。 (我认为这符合维基百科上的定义)

更具体地说，以下是我想要实现的示例，其中一个是用命令式编程编写的，运行时间为 O(n)，另一个示例是函数式编程，运行时间为 O(n^2)。

fun prefixSumsImperative(numbers: IntArray): IntArray {
    val prefixSums = IntArray(numbers.size)
    var prefixSum = 0
    for ((i, number) in numbers.withIndex()) {
        prefixSum += number
        prefixSums[i] = prefixSum
    }
    return prefixSums
}

fun prefixSumsFunctionalONSquared(numbers: IntArray): IntArray =
    (0 until numbers.size).map { numbers.take(it).sum() }.toIntArray()

Answer 1

从 Kotlin 1.4 开始，您可以使用 scan 和 runningFold 函数来实现此目的:

fun prefixSumsFunctional(numbers: IntArray): IntArray =
    numbers.runningFold(0) { sum, num ->
        sum + num
    }.toIntArray()