Logarithmic reduce

[soronpo]

In my use-cases I often found myself requiring a logarithmic reduce that applies LogN operations on a collection, instead of N-1 operations.
What do you think? Is this a worthy addition?

[NthPortal]

What do you mean by logarithmic reduce?

Do you mean that it reduces pairs of elements, and the pairs those results and reduces them, until you have a single result? If so, that ends up being n-1 anyway. And even if I'm wrong on that, the first round is n/2, which is O(n) anyway.

I'm pretty sure you can't do better than O(n) for a reduce - it has to touch all of the elements.

[soronpo]

Oh, yes you're right, I'm sorry, I was looking at it from a concurrent perspective where I build a balanced tree of operations to run later. So a regular reduce will be a left/right-side biased. A logarithmic reduce will create a balanced construction of the tree, LogN in height, so with N/2 workers at most each execution unit takes in LogN steps to complete.

[NthPortal]

I think that's more of a parallel collections thing (although it might be doable just with Stepper?)

[soronpo]

There is nothing parallel in the reduce itself. The traversal just needs to be logarithmic.

[NthPortal]

I guess I'm not understanding the value of a method that creates a balanced construction (which inevitably takes up more memory) for O(log(n)) steps if there's no way to parallelise it

[Sciss]

you mean like a finger tree?