How to reduce a limited stream (e.g. an ArrayList) from right in Java?

Question

I would like to convert a list to a self-implemented linked list using reduce. I managed to do that in a reverse order:

import java.util.Arrays;
import java.util.List;

public class Reverse {
    static class Node {
        int val;
        Node next;

        Node(int v, Node n) {
            val = v;
            next = n;
        }
    }

    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6);
        Node result = numbers
                .stream()
                .reduce(null,
                        (node, val) -> new Node(val, node),
                        (n1, n2) -> new Node(-1, null));

        while(result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }
}

Output is

I think to obtain result in the correct order, I may have to use something like foldRight or reduceRight in other languages. Does java provide anything similar, given that the stream is guaranteed to be limited?

[this](https://stackoverflow.com/questions/41240414/equivalent-of-scalas-foldleft-in-java-8) might be related if not duplicate — Naman, Apr 26 '21 at 05:56

the Hutt · Answer 1 · 2021-04-26T03:45:38.353

You can provide identity and use it as starting point:

public class Test {

    public static void main(String[] args) throws Exception {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6);
        Node result = new Node();

        numbers.stream()
           .reduce(result,
                  (node, val) -> {node.next= new Node(val, null); return node.next;},
                  (n1, n2) -> new Node(-1, null));

        result = result.next;
        while(result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }
}
class Node {
    int val;
    Node next;

    Node(){}
    Node(int v, Node n) {
        val = v;
        next = n;
    }
}

Output:

Hacky but neat technique. Reminds me of the good old days using C pointers. — wlnirvana, Apr 26 '21 at 07:06

score 0 · Accepted Answer · answered Apr 26 '21 at 03:27

As of the newest Java 16, the current Stream API doesn't provide any operations "from the right" such as "reduceRight`.

The only possible workaround is to use Collections#reverse(List) method to reverse the order of the items in the collection right before applying reduction.

List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6);
Collections.reverse(numbers);
Node result = numbers
    .stream()
    .reduce(null,
            (node, val) -> new Node(val, node),
            (n1, n2) -> new Node(-1, null));

Read more here: Java 8 stream reverse order

score 0 · Answer 3 · answered Apr 26 '21 at 03:46

Streams are, as their name suggests, one-directional things. They are like production lines. You can't just go "give me the last item on the line first!" because the conveyor belts don't work that way. You can wait at a point on the line to collect all the items, and as you collect them, order them in the reverse order. Then put them on the production line again.

numbers.stream().collect(Collectors.toCollection(ArrayDeque::new)).stream()
    .reduce(...)

Here I have collected it into an ArrayDeque, and since ArrayDeque is a stack structure, it reverses it. Then you can go through it with reduce.

Note that the "reversing the list" part doesn't need streams at all:

new ArrayDeque<>(number).stream().reduce(...)
// or the many other ways of reversing a list

In any case, you are going through the list twice. If you want to do this by going through the list once, one way I can think of is to use a mutating reduction to keep track of where the tail of the linked list is.

You need an extra helper object to keep track of the tail:

static class CollectHelper {
  private Node tail;
  private Node head;

  public void accumulate(int i) {
    if (head == null) {
      head = new Node(i, null);
      tail = head;
    } else {
      tail.next = new Node(i, null);
      tail = tail.next;
    }
  }

  public void combine(CollectHelper other) {
    if (other.head == null) return;
    tail.next = other.head;
    tail = other.tail;
  }
}

Then you can do:

Node result = numbers
    .stream()
    .collect(CollectHelper::new, CollectHelper::accumulate, CollectHelper::combine).head;

How to reduce a limited stream (e.g. an ArrayList) from right in Java?

3 Answers3