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

Question

Is it possible to compute all prefix sums for an array of numbers in purely functional programming style in O(n) time in Kotlin?

What I mean by purely functional programming is allowing using functional programming extension functions for collections only, such as map, reduce, fold, sum, etc. in _Collections,kt, while traditional imperative programming methods involving changing state and mutable data such as ordinary loops, mutable variables aka vars, and mutable arrays are not allowed. (I think this conforms to the definition on Wikipedia)

To be more specific, here are one example of what I want to achieve written in imperative programming that runs in O(n) time, and another in functional programming that runs in O(n^2) time.

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

Unfortunately, solving this problem requires persistent stack, which is not presented in standard Kotlin library. But stack can be imitated with 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()