Does Kotlin have something similar to RxJava scan?


#1

I have a simple list (or sequence) of Pair(charSequence, Int)

(C0, 0), (C1, 1), (C2, 2), (C3, 3), …

I would like to accumulate the ints and produce
(C0, 0), (C1, 1), (C2, 3), (C3, 6)

It’s quite easy to do in imperative style, but what about fonctionnal style :
Is there a way to do that with an operator on lists/sequences in Kotlin ? with Java8 and streams ?

It is possible to do in RxJava with the operator scan
http://reactivex.io/documentation/operators/scan.html

Also, I often wonder if the Kotlin operators on iterable/sequences in the std lib are not a bit lacking compared to RxJava operators/transformers.
The RxJava api seems a lot more full featured while not being bloated


Reductions / cumulative sum
#2

I second the need for this. Basically scan is like fold except that instead of giving you just the last value it gives you the seed and all intermediate values


#3

I am third. It would really useful function


#4

Hi there you could implement this easily like so:

fun <S, T : S> List<T>.scan(op: (S, T) -> S): List<S> {
  return this.mapIndexed { i, _ ->
    this.subList(0, i + 1).reduce(op)
  }
}

#5

@tommot1985 I wouldn’t recommend to use such implementation, as it has quadratic time complexity: for every element it needs to redo the operation for all elements before that one.

We’re considering to introduce functions like scan in this issue: KT-7657.


#6

I have thought up two versions with linear runtime (not checked):
With mutable state:

fun <S, T : S> List<T>.scan(op: (S, T) -> S): List<S> {
   var accumulator: S = this[0]
   return this.mapIndexed { i, x ->
     if (i != 0) {
       accumulator = op(accumulator, x)
     }
     accumulator
   }
}

and without mutable state:

fun <S, T : S> List<T>.scan(op: (S, T) -> S): List<S> {
  fun tempFun(accumulator: S, list: List<T>, op: (S, T) -> S): List<S> {
    val result = op(accumulator, list.first())
    val cdr = list.drop(1)
    if (cdr.size > 0) {
      return listOf<S>(result) + tempFun(result, cdr, op)
    }
    return listOf<S>(result)
  }
  return listOf<S>(this[0]) + tempFun(this[0], this.drop(1), op)
}

#7

I developed a Kotlin library of immutable datatypes.
The List class includes the scanLeft member function which should meet your needs.
The documentation taken from the function is:

/**
* scanLeft is similar to foldLeft, but returns a list of successively
* reduced values from the left.
*
* Examples:
* [4, 2, 4].scanLeft(64){m, n -> m / y} = [64, 16, 8, 2]
* .scanLeft(3){m, n -> m / y} = [3]
* [1, 2, 3, 4].scanLeft(5){m, n -> if (m > n) m else n} = [5, 5, 5, 5, 5]
* [1, 2, 3, 4, 5, 6, 7].scanLeft(5){m, n -> if (m > n) m else n} = [5, 5, 5, 5, 5, 5, 6, 7]
*
* @param f uncurried binary function
* @param e initial value
* @return new list
*/

The library can be found here.


#8

I might be wrong here, but the solution I’m using seems pretty trivial in implementation and with little preformance degradation:

fun <T, R: Any> List<T>.scan(op: (T, T) -> R): List<R> {
    return if(size > 1) {
        mapIndexedNotNull{ index, t ->
            if(index < size - 1) {
                op(get(index), get(index + 1))
            } else {
                null
            }
        }
    } else {
        emptyList()
    }
}