Вычислить все суммы префиксов в чисто функциональном стиле программирования за O (n) раз в Kotlin

Question

Можно ли вычислить все суммы префиксов для массива чисел в чисто функциональном программировании в стиле O (n) в Kotlin?

Что я имею в виду под чисто функциональным программированием:разрешить использование функций расширения функционального программирования только для коллекций, таких как map, reduce, fold, sum и т. д. в _Collections, kt , в то время как традиционные методы императивного программирования включают изменение состояния иИзменяемые данные, такие как обычные циклы, изменяемые переменные, такие как 1011 * s, и изменяемые массивы не допускаются. (Я думаю, что это соответствует определению в Википедии)

Чтобы быть более конкретным, вот один пример того, чего я хочу достичь, написанного в императивном программировании, которое выполняется за время 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. Но стек можно имитировать парами:

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 2

Это решение отвечает всем вашим требованиям, для функционального стиля:

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