4

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()
Shreck Ye
  • 1,591
  • 2
  • 16
  • 32
  • 1
    The helper function you'd be looking for is often called [a `scan`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html#v:scanl), but does't appear to be available in Kotlin. You can emulate it though by building a linked list in a `fold` operation and reversing it afterwards (or doing `foldRight`). – Bergi Oct 16 '19 at 01:44
  • Update: [scan](https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/scan.html) is available in Kotlin now, though it's temporarily experimental. – Shreck Ye May 06 '20 at 07:16

3 Answers3

3

As of Kotlin 1.4 you can use scan and runningFold functions for this purpose:

fun prefixSumsFunctional(numbers: IntArray): IntArray =
    numbers.runningFold(0) { sum, num ->
        sum + num
    }.toIntArray()
Rjbcc58
  • 176
  • 2
  • 14
1

This solution meets all your requirements, for a functional style:

fun prefixSumsFunctional(numbers: IntArray): IntArray =
    numbers.fold(listOf<Int>()) { result, el ->
        if (result.isEmpty()) {
            result + el
        } else {
            result + (result.last() + el)
        }
    }.toIntArray()
Rene
  • 5,730
  • 17
  • 20
  • 2
    It runs in _O(n^2)_ because of the list connection running in _O(n)_. – IlyaMuravjov Oct 15 '19 at 20:12
  • 1
    @Bananon Yes you are right, but this is only a problem of this list implementation. I could use Vavr or some other persistent list. – Rene Oct 15 '19 at 20:40
  • Could it be argued `fold` violates the definition of purely functional the OP gave? It basically provides a mutable variable to use alongside your function. – Tenfour04 Oct 15 '19 at 21:04
  • 4
    @Tenfour04 `fold` doesn't provide a mutable variable, it only guarantees that it will give you the value which was returned at the previous step. You can even implement `fold` without using `var` keyword: `tailrec fun 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`. – IlyaMuravjov Oct 15 '19 at 21:16
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()
IlyaMuravjov
  • 2,352
  • 1
  • 9
  • 27