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

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

我所说的纯函数式编程是指仅对集合使用函数式编程扩展功能，例如_Collections,kt中的map，reduce，fold，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()

最佳答案

不幸的是，解决此问题需要持久性堆栈，而标准Kotlin库中没有提供持久性堆栈。但是堆栈可以用成对模仿:

fun prefixSumsFunctionalPuzzler(numbers: IntArray): IntArray =
    generateSequence(numbers.fold(Any() to 0) { stack, value ->
        stack to stack.second + value
    }) { it.first as Pair<Any, Int> }
        .map { it.second }
        .take(numbers.size)
        .toList().asReversed().toIntArray()