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

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

Под чисто функциональным программированием я подразумеваю использование функций расширения функционального программирования только для коллекций, таких как 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()

kotlin functional-programming purely-functional prefix-sum
person Shreck Ye    schedule 15.10.2019    source источник
comment
Вспомогательная функция, которую вы ищете, часто называется a scan, но, похоже, недоступен в Kotlin. Однако вы можете подражать этому, построив связанный список в fold операции, а затем перевернув его (или выполнив foldRight).   -  person Bergi    schedule 16.10.2019
comment
Обновление: сканирование теперь доступно в Котлине, хотя это временно экспериментально.   -  person Shreck Ye    schedule 06.05.2020

Ответы (3)


arrow_upward
1
arrow_downward

К сожалению, для решения этой проблемы требуется постоянный стек, которого нет в стандартной библиотеке 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()
person Bananon    schedule 15.10.2019
comment
Вы можете использовать generateSequence вместо Stream.iterate. - person Rene; 16.10.2019

arrow_upward
1
arrow_downward

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

fun prefixSumsFunctional(numbers: IntArray): IntArray =
    numbers.fold(listOf<Int>()) { result, el ->
        if (result.isEmpty()) {
            result + el
        } else {
            result + (result.last() + el)
        }
    }.toIntArray()
person Rene    schedule 15.10.2019
comment
Он выполняется в O (n ^ 2), потому что соединение со списком выполняется в O (n). - person Bananon; 15.10.2019
comment
@Bananon Да, вы правы, но это только проблема реализации этого списка. Я мог бы использовать Вавр или какой-нибудь другой постоянный список. - person Rene; 15.10.2019
comment
Можно ли утверждать, что fold нарушает определение чисто функционального, данное OP? По сути, он предоставляет изменяемую переменную для использования вместе с вашей функцией. - person Tenfour04; 16.10.2019
comment
@ Tenfour04 fold не предоставляет изменяемую переменную, он только гарантирует, что он вернет вам значение, которое было возвращено на предыдущем шаге. Вы даже можете реализовать fold без использования ключевого слова var: tailrec fun <R> IntArray.fold(initial: R, start: Int = 0, operation: (acc: R, Int) -> R): R = if (start < size) fold(operation(initial, this[start]), start + 1, operation) else initial. - person Bananon; 16.10.2019

arrow_upward
1
arrow_downward

Начиная с Kotlin 1.4 для этой цели можно использовать функции scan и runningFold:

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