Java 8 functional style to iterate with indexes

Question

I have been practicing java 8 streams and functional style for a while. Sometimes I try to solve some programming puzzles just using streams. And during this time I found a class of tasks which I don't know how to solve with streams, only with classical approach.

One example of this kind of tasks is: Given an array of numbers find index of the element which will make sum of the left part of array below zero. e.g. for array [1, 2, 3, -1, 3, -10, 9] answer will be 5

My first idea was to use IntStream.generate(0, arr.length)... but then I don't know how to accumulate values and being aware of index same time.

So questions are:

Is it possible to somehow accumulate value over stream and then make conditional exit?
What is then with parallel execution? it's not fitting to problem of finding indexes where we need to be aware of elements order.

Hardly possible with stream API as this problem requires tracking non-local state (sum of all prefix elements) which is also bound to the element order. Stream API is designed to make parallel processing as easy as sequential, but such kind of operations is sequential by nature... — Tagir Valeev, Dec 21 '15 at 13:19
Possible duplicate of http://stackoverflow.com/questions/22789413/what-are-the-reasons-for-not-having-an-index-in-java-8-streams and http://stackoverflow.com/questions/28989841/how-to-map-elements-of-the-list-to-their-indices-using-java-8-streams. — Brian Goetz, Dec 21 '15 at 16:44

Alexis C. · Accepted Answer · 2015-12-21T13:57:00.567

I doubt your task is well suited for streams. What you are looking for is a typical scan left operation which is by nature a sequential operation.

For instance imagine the following elements in the pipeline: [1, 2, -4, 5]. A parallel execution may split it into two subparts namely [1, 2] and [-4, 5]. Then what would you do with them ? You cannot sum them independently because it will yields [3] and [1] and then you lost the fact that 1 + 2 - 4 < 0 was respected.

So even if you write a collector that keeps track of the index, and the sum, it won't be able to perform well in parallel (I doubt you can even benefit from it) but you can imagine such a collector for sequential use :

public static Collector<Integer, ?, Integer> indexSumLeft(int limit) {
        return Collector.of(
                () -> new int[]{-1, 0, 0},
                (arr, elem) -> {
                    if(arr[2] == 0) {
                        arr[1] += elem;
                        arr[0]++;
                    }
                    if(arr[1] < limit) {
                        arr[2] = 1;
                    }

                },
                (arr1, arr2) -> {throw new UnsupportedOperationException("Cannot run in parallel");},
                arr -> arr[0]

        );
    }

and a simple usage:

int index = IntStream.of(arr).boxed().collect(indexSumLeft(0));

This will still traverse all the elements of the pipeline, so not very efficient.

Also you might consider using Arrays.parallelPrefix if the data-source is an array. Just compute the partial sums over it and then use a stream to find the first index where the sum is below the limit.

Arrays.parallelPrefix(arr, Integer::sum);
int index = IntStream.range(0, arr.length)
                     .filter(i -> arr[i] < limit)
                     .findFirst()
                     .orElse(-1);

Here also all the partial sums are computed (but in parallel).

In short, I would use a simple for-loop.

Nice. Didn't know about parallelPrefix. Thank you! – Igor Konoplyanko Dec 21 '15 at 13:56 — Igor Konoplyanko, Dec 21 '15 at 13:56

score 4 · Answer 2 · answered Dec 21 '15 at 13:28

I can propose a solution using my StreamEx library (which provides additional functions to the Stream API), but I would not be very happy with such solution:

int[] input = {1, 2, 3, -1, 3, -10, 9};
System.out.println(IntStreamEx.of(
    IntStreamEx.of(input).scanLeft(Integer::sum)).indexOf(x -> x < 0));
// prints OptionalLong[5]

It uses IntStreamEx.scanLeft operation to compute the array of prefix sums, then searches over this array using IntStreamEx.indexOf operation. While indexOf is short-circuiting, the scanLeft operation will process the whole input and create an intermediate array of the same length as the input which is completely unnecessary when solving the same problem in imperative style.

score 2 · Answer 3 · answered Jan 24 '16 at 08:32

With new headTail method in my StreamEx library it's possibly to create lazy solution which works well for very long or infinite streams. First, we can define a new intermediate scanLeft operation:

public static <T> StreamEx<T> scanLeft(StreamEx<T> input, BinaryOperator<T> operator) {
    return input.headTail((head, tail) -> 
               scanLeft(tail.mapFirst(cur -> operator.apply(head, cur)), operator)
                   .prepend(head));
}

This defines a lazy scanLeft using the headTail: it applies given function to the head and the first element of the tail stream, then prepends the head. Now you can use this scanLeft:

scanLeft(StreamEx.of(1, 2, 3, -1, 3, -10, 9), Integer::sum).indexOf(x -> x < 0);

The same can be applied to the infinite stream (e.g. stream of random numbers):

StreamEx<Integer> ints = IntStreamEx.of(new Random(), -100, 100)
                                    .peek(System.out::println).boxed();
int idx = scanLeft(ints, Integer::sum).indexOf(x -> x < 0);

This will run till the cumulative sum becomes negative and returns the index of the corresponding element.

Java 8 functional style to iterate with indexes

3 Answers3