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 var
s, 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()
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()