Java 8 将列表缩减为链表

Question

我的问题基本上归结为将 List 缩减为链表，但从 reduce 函数推断的类型似乎不正确。

我的列表将如下所示

[0, 1, 2]

我希望 reduce 函数在每个 reduce 步骤都这样做

null                            // identity (a Node)
Node(0, null)                   // Node a = null, int b = 0
Node(1, Node(0, null))          // Node a = Node(0, null), int b = 1
Node(2, Node(1, Node(0, null))) // Node a = Node(1, Node(0, null)), int b = 2

然而，reduce 函数似乎认为这行不通，因为我猜它不认为身份是一个节点。

这是我的代码。

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Example {
    static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    static Node reverse(List<Integer> list) {
        return list.stream()
                .reduce(null, (a, b) -> new Node(b, a)); // error: thinks a is an integer
    }

    void run() {
        List<Integer> list = IntStream.range(0, 3)
                .boxed()
                .collect(Collectors.toList());
        Node reversed = reverse(list);
    }

    public static void main(String[] args) {
        new Example().run();
    }
}

我做错了什么？

编辑接受答案后，我的代码如下所示：

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Example {
    static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", next=" + next +
                    '}';
        }
    }

    static Node reverse(List<Integer> list) {
        return list.stream()
                .reduce(null, (n, i) -> {
                    System.out.println("Will happen"); // to demonstrate that this is called
                    return new Node(i, n);
                }, (n1, n2) -> {
                    System.out.println("Won't happen"); // and this never is
                    return new Node(n1.value, n2);
                });
    }

    void run() {
        List<Integer> list = IntStream.range(0, 3)
                .boxed()
                .collect(Collectors.toList());
        Node reversed = reverse(list);
        System.out.println(reversed);
    }

    public static void main(String[] args) {
        new Example().run();
    }
}

现在打印

Will happen
Will happen
Will happen
Node{value=2, next=Node{value=1, next=Node{value=0, next=null}}}

我仍然不知道为什么 Java 不能告诉 reduce 函数的第三个参数是不必要的，它永远不会被调用，但这是另一天的问题。

第二次编辑

可以像这样为 reduce 操作创建一个新方法，因为 reduce 的第三个参数可以只是一个什么都不做的函数。

static <T, U> U reduce(Stream<T> stream, U identity, BiFunction<U, ? super T, U> accumulator) {
    return stream.reduce(identity, accumulator, (a, b) -> null);
}

static Node reverse(List<Integer> list) {
    return reduce(list.stream(), null, (n, i) -> new Node(i, n));
}

Answer 1

你遇到的问题是 reduce 期望 return 它积累的相同类型。在这种情况下 null 和 a

一样是 Integer

你可以做的是将每个 Integer 映射到一个 Node，然后将节点缩减为链表。

static Node reverse(List<Integer> list) {
    return list.stream()
            .map(i -> new Node(i, null))
            .reduce(null, (a, b) -> {
                b.next = a;
                return b;
            });
}

void run() {
    List<Integer> list = IntStream.range(0, 3)
            .boxed()
            .collect(Collectors.toList());
    Node reversed = reverse(list);
    for(Node n = reversed; n != null ; n = n.next)
        System.out.println(n.value);
}

打印

2
1
0

Answer 2

您可以使用另一个 reduce 运算符，做

    static Node reverse(List<Integer> list) {
      return list.stream()
        .reduce(
          (Node) null, //the empty element
          (n, i) -> new Node(i, n) , //combining a Node and an Integer
          (n1, n2) -> new Node(n1.value, n2)); // could be anything
    }

编辑：使其与 parallelStream 一起工作：

    public static Node merge(Node n1, Node n2) {
        if (n1 == null) {
            return n2;
        } else {
            return new Node(n1.value, merge(n1.next, n2));
        }
    }

    static Node reverse(List<Integer> list) {
      return list.stream()
        .reduce(
          (Node) null, //the empty element
          (n, i) -> new Node(i, n) , //combining a Node and an Integer
          (n1, n2) -> merge(n1, n2)); // combining two Nodes
    }

Java 8 将列表缩减为链表

Java 8 reduce list to linkedlist

java

reduce

linked-list

java-8