I know that Kotlin has ‘reduce.’ I want to know if there is support for ‘reductions.’
For example, reduce + [1 2 3 4 5] = 15
reductions + [1 2 3 4 5] = 0, 1, 3, 6, 10, 15
Does Kotlin List have a builtin for reductions?
1 Like
Not that I know of.
I don’t even understand what is question about.
1 Like
@darksnake What is a function that (presumably efficiently) provides a list of the reductions you would get if you were to reduce the first n elements where n is the index (or perhaps index+1). Obviously the naive approach is fairly straightforward, but also hopelessly inefficient. The correct implementation would basically provide a list of the intermediates (rather than swallowing them as reduce does). And as far as I know the standard library doesn’t carry such a function.
1 Like
Well, this should not be too hard to implement yourself.
fun <T, R> Iterable<T>.reductions(initial: R, operation: (acc: R, T) -> R) : Sequence<R> = buildSequence {
var last = initial
forEach {
last = operation(last, it)
yield(last)
}
}
I based this on the link you posted, which does not return the initial value in the sequence, but you can easily change that.
Just out of interest, what do you need this for. I never used something like this, but maybe it’s worth extending the stdlib.
1 Like
Thanks!
I agree it is not difficult to implement. I was curious whether it was part of stdlib.
One use for this is “cumulative sum”, which is defined as (reductions + lst).
Two uses of “cumulative sum” are:
-
it allows you to in O(1) time compute the sum of any range, so the sum of elements [i, …, j] is just sum[j+1] - sum[i]
-
this is also useful in geometric applications when you have a bunch of boxes that are placed one after another, and you want their x coordinates – the sum[i] will give the x coord of object i+1
-
if you do this on a 2d grid, you compute the ‘integral image’, which has lots of applications in computer vision
-
this is a matlab builtin: Cumulative sum - MATLAB cumsum (probably numpy too), so lots of other applications
1 Like
Cumulative sum operation has very narrow application. It is not needed in standard library. I’ve added it to todo list for math library, but I don’t know when I have time to return to the project (I hope soon).
-
I never suggested adding cumulative sum to stdlib.
-
I do think ‘reductions’ is a nice addition to stdlib.
-
The examples of cumulative sum was in response to @Wasabi375 asking what I was using it for – namely a bunch of gfx / image manipulation tasks.i
Kotlin stdlib does have reduction, just not the cumulative one.
I don’t like how your comments take my statements out of context to twist their meaning.
-
I never suggested adding cumulative sum to stdlib.
-
I stated upfront that “reduce” is part of stdlib.
It almost seems like you are ignoring the overall discussion and pedantically looking for points to disagree on.
I think that is a bit harsh. I guess his comment about not wanting to add cumulative sum to stdlib was in response to me asking about extending the stdlib.
Yes you did, but as you did this in the first post I can understand why he might have overlooked it as I also don’t read every post in here (a second time) when I reply.
Let’s not argue about a simple misunderstanding and keep it to the topic.
Sorry, the first post was a little bit vague.
I do not disagree with you. On the contrary, such extensions are needed, just not in the standard library. Matlab and numpy have it since they are math oriented. Kotlin is not math oriented as it is, but it could be a great tool for mathematics and science, just with correct set of scientific libraries.
I apologize if my previous post came off as overly critical. I wanted to clearly define what I was/was-not arguing for.
I agree that “cumulative sum” is a “math function.” I mentioned cumulative sum as a demonstration of the power of “reductions” – i.e. “this commonly used math function is merely (reductions +)”
I don’t see “reductions” as a “math function”.
I see “reductions” as a “list function”, on the same level as map, filter, reduce (left fold, right fold).
in fact, lst.map(f) = lst.reductions{ (old_state, x) → f(x) }
The question is still whether or not to add this to the stdlib. I personally have nothing against the idea, but then I don’t program for android. I’m have no idea about the current state of the art, but I thought multidex is at least not a given. That being said, I don’t really think 2 methods more to the stdlib hurt anyone (except this one project which has exactly 65536 methods 
).
That being said, I see a situation where I would need this function except for mathematical/statistical reasons in which case they belong in maths library.
-
I only use Kotlin - JVM/JS, so I completely failed to take Android limitations (size, method count, …) into consideration.
-
I don’t know if the following falls under “math/statistics”. I’m creating a texture atlas: Texture atlas - Wikipedia
Each glyph has a bounding box of (width x height). I have a pretty stupid algorithm where I sort the glyphs by height, then I place them adjacent to each other.
This ends up in a situation where, for any given line, the x coordinates of the glyphs end up being:
boxes.reductions { (old, it) → old + it.width }
- If it was just JVM/JS, I would argue for adding “reductions” – in light of android limitations, I have no idea.
We’re discussing whether to add such family of functions in https://youtrack.jetbrains.com/issue/KT-7657.
Currently we need names to distinguish reduction with/without initial values, similar to the existing fold/reduce functions.
@ikt If you have use cases for such functions, please do not hesitate to share them in that issue.
1 Like
Here is a related thread on the topic: Does Kotlin have something similar to RxJava scan?
I know I have needed this functionality multiple times in the past and I know that rxjava has it as the scan function but do not remember the specific use cases I had. Here is an issue I opened on a Java streaming API to add similar operators, but it didn’t have significant use cases.
I know I needed something related to do a flow style layout where I have an iterable list of items that all had a width property and I wanted to group them into collections based on how they fit on lines. This is more complex case I know but does involve similar summing of cumulative items.
I disagree with others that say this should not be in the stdlib. It is like reduce except that instead of only giving you the result of all items it gives you the result on each item.