递归使用Stream.flatMap()

Question

考虑以下类:

public class Order {
    private String id;
    private List<Order> orders = new ArrayList<>();
    @Override
    public String toString() {
        return this.id;
    }
    // getters & setters
}

注意:需要注意的是，我不能修改这个类，因为我是从外部API消费它的。

还要考虑以下顺序层次结构:

Order o1 = new Order();
o1.setId("1");
Order o11 = new Order();
o11.setId("1.1");
Order o111 = new Order();
o111.setId("1.1.1");
List<Order> o11Children = new ArrayList<>(Arrays.asList(o111));
o11.setOrders(o11Children);
Order o12 = new Order();
o12.setId("1.2");
List<Order> o1Children = new ArrayList<>(Arrays.asList(o11, o12));
o1.setOrders(o1Children);
Order o2 = new Order();
o2.setId("2");
Order o21 = new Order();
o21.setId("2.1");
Order o22 = new Order();
o22.setId("2.2");
Order o23 = new Order();
o23.setId("2.3");
List<Order> o2Children = new ArrayList<>(Arrays.asList(o21, o22, o23));
o2.setOrders(o2Children);
List<Order> orders = new ArrayList<>(Arrays.asList(o1, o2));

可以这样直观地表示:

1
1.1
1.1.1
1.2
2
2.1
2.2
2.3

现在，我想把这个层次结构的顺序平铺成一个List，这样我就得到了以下内容:

[1, 1.1, 1.1.1, 1.2, 2, 2.1, 2.2, 2.3]

我已经设法通过递归地使用flatMap()(以及helper类)来做到这一点，如下所示:

List<Order> flattened = orders.stream()
    .flatMap(Helper::flatten)
    .collect(Collectors.toList());

这是辅助类:

public final class Helper {
    private Helper() {
    }
    public static Stream<Order> flatten(Order order) {
        return Stream.concat(
            Stream.of(order), 
            order.getOrders().stream().flatMap(Helper::flatten)); // recursion here
    }
}

下一行:

System.out.println(flattened);

产生以下输出:

[1, 1.1, 1.1.1, 1.2, 2, 2.1, 2.2, 2.3]

到目前为止一切顺利。结果是绝对正确的。

然而，在阅读这个问题之后，我对递归方法中flatMap()的使用有一些担忧。特别是，我想知道流是如何扩展的(如果这是术语的话)。所以我修改了Helper类，并使用peek(System.out::println)来检查:

public static final class Helper {
    private Helper() {
    }
    public static Stream<Order> flatten(Order order) {
        return Stream.concat(
            Stream.of(order), 
            order.getOrders().stream().flatMap(Helper::flatten))
        .peek(System.out::println);
    }
}

输出为:

1
1.1
1.1
1.1.1
1.1.1
1.1.1
1.2
1.2
2
2.1
2.1
2.2
2.2
2.3
2.3

我不确定这是否是应该打印的输出。

所以，我想知道是否可以让中间流包含重复的元素。此外，这种方法的优缺点是什么?毕竟，这样使用flatMap()是正确的吗?有更好的方法来达到同样的效果吗?

Answer 1

嗯，我使用了与通用Tree类相同的模式，并且没有错误的感觉。唯一的区别是，Tree类本身提供了children()和allDescendants()方法，两者都返回Stream，后者以前者为基础。这与"我应该返回一个集合还是一个流?"one_answers"命名返回流的java方法"。

从 Streams的角度来看，flatMap对不同类型的子节点(即遍历属性时)和flatMap对相同类型的子节点没有区别。如果返回的流再次包含相同的元素也没有问题，因为流的元素之间没有关系。原则上，可以使用模式flatMap(x -> condition? Stream.of(x): Stream.empty())将flatMap用作filter操作。也可以使用它来复制元素，就像下面这个答案一样。

Answer 2

以这种方式使用flatMap确实没有问题。流中的每个中间步骤都是完全独立的(按照设计)，因此递归中没有风险。您需要注意的主要事情是在流式传输时可能会改变底层列表的任何内容。对你方而言，这似乎不构成风险。

理想情况下，您应该将此递归作为Order类本身的一部分:

class Order {
    private final List<Order> subOrders = new ArrayList<>();
    public Stream<Order> streamOrders() {
        return Stream.concat(
            Stream.of(this), 
            subOrders.stream().flatMap(Order::streamOrders));
    }
}

然后你可以使用orders.stream().flatMap(Order::streamOrders)，这对我来说似乎比使用助手类更自然。

作为一个有趣的问题，我倾向于使用这些类型的stream方法来允许使用集合字段而不是字段的getter。如果方法的用户不需要知道底层集合的任何信息，或者不需要能够更改它，那么返回一个流是方便和安全的。

我要注意的是，在你的数据结构中有一个你应该意识到的风险:一个订单可能是其他几个订单的一部分，甚至可能是它自己的一部分。这意味着导致无限递归和堆栈溢出非常简单:

Order o1 = new Order();
o1.setOrders(Arrays.asList(o1));
o1.streamOrders();

有很多好的模式可以避免这类问题，所以如果你需要这方面的帮助，请询问。

你指出你不能改变Order类。在这种情况下，我建议您扩展它以创建自己的更安全的版本:

class SafeOrder extends Order {
    public SafeOrder(String id) {
        setId(id);
    }
    public void addOrder(SafeOrder subOrder) {
        getOrders().add(subOrder);
    }
    public Stream<SafeOrder> streamOrders() {
        return Stream.concat(Stream.of(this), subOrders().flatMap(SafeOrder::streamOrders));
    }
    private Stream<SafeOrder> subOrders() {
        return getOrders().stream().map(o -> (SafeOrder)o);
    }
}

这是一个相当安全的强制转换，因为您希望用户使用addOrder。不是万无一失的，因为他们仍然可以调用getOrders并添加Order而不是SafeOrder。如果你感兴趣的话，这里有一些模式可以防止这种情况。