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

Question

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

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

更具体地说，这是我想要实现的一个例子，它是在 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

此解决方案满足您对功能样式的所有要求：

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

Answer 2

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

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

从 Kotlin 1.4 开始，您可以为此目的使用 scan 和 runningFold 函数：

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

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

Compute all prefix sums in purely functional programming style in O(n) time in Kotlin

kotlin

functional-programming

purely-functional

prefix-sum