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

Question

是否可以在 Kotlin 的 O(n) 时间内以纯函数式编程风格计算数组的所有前缀和？

我所说的纯函数式编程的意思是允许仅对集合使用函数式编程扩展函数，例如_Collections,ktmap中的,reduce​​ , fold,sum等，而传统的命令式编程方法涉及更改状态和可变数据，例如普通循环，又名可变变量s，并且不允许使用可变数组。（我认为这符合维基百科上的定义）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()

Answer 2

不幸的是，解决这个问题需要持久堆栈，标准 Kotlin 库中没有。但是stack可以用pairs来模仿：

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()

Answer 3

该解决方案满足您对功能风格的所有要求：

fun prefixSumsFunctional(numbers: IntArray): IntArray =
    numbers.fold(listOf<Int>()) { result, el ->
        if (result.isEmpty()) {
            result + el
        } else {
            result + (result.last() + el)
        }
    }.toIntArray()