如何收集递归方法的结果

Question

我遍历树结构以收集叶节点的路径.您希望以哪种方式收集操作结果:

a)合并孩子的结果并返回

private Collection<String> extractPaths(final Element element, final IPath parentPath) {
    final IPath path = parentPath.append(element.getLabel());
    final Collection<Element> children = getElementChildren(element);
    if (children.isEmpty())
        return Collections.singletonList(path.toString());

    final Set<String> result = new TreeSet<String>();
    for (final Element child : children)
        result.addAll(extractPaths(child, path));
    return result;
}

b)提供结果集合作为参数,并在每个递归步骤中添加新元素

private void extractPaths(final Element element, final IPath parentPath, final Set<String> result) {
    final IPath path = parentPath.append(element.getLabel());
    final Collection<Element> children = getElementChildren(element);
    if (children.isEmpty())
        result.add(path.toString());

    for (final Element child : children)
       extractPaths(child, path, result);
}

Answer 1

两者都可以毫无问题地使用.虽然,以前的解决方案更干净,因为它不会改变输入参数.功能编程的本质没有任何副作用.

Answer 2

我假设后者打算打电话extractPaths(child, path, result)？

后一种形式将更有效,因为它不需要在每个递归级别复制项目.正如Boris所说,它在功能上不那么干净 - 但Java并没有真正为不可变集合提供适当的方法来有效地创建基于它们的新集合.

在使调用愉快方面,您可以提供第一个选项样式的包装器,它只创建一个新集合并调用第二个选项.这可能就是我要做的事情:

private Collection<String> extractPaths(Element element, IPath parentPath) {
    Set<String> ret = new HashSet<String>();
    extractPaths(element, parentPath, ret);
    return ret;
}

另一种方法是将第三个参数从a更改为Set<String>某种"收集器"界面:您告诉它您已找到结果,而没有指定如何处理它.实际上,收集器可以返回一个新的收集器,从那时开始使用 - 将其留给实现来决定是否制作功能上干净的"创建新的"版本,或者隐藏收集器中的副作用本身再次重复使用.

Answer 3

经过一些重构后我发现的最终解决方案是实现变体 b) 但传递 Visitor 而不是结果集合：

private void traverse(final Element element, final Visitor... visitors) {
   for (final Visitor visitor : visitors)
       // push e.g. the parent path to the stack
       visitor.push(visitor.visit(element)); 

   for (final Element child: getElementChildren(element))
       traverse(child, visitors);

   for (final Visitor visitor : visitors)
       visitor.pop();
}

Visitor还提供了一个堆栈来携带有关父路径的信息。这个解决方案允许我将遍历逻辑与集合逻辑分开，而不需要更复杂的 TreeIterator 实现。

private class CollectPathsVisitor extends ElementVisitor {
    public final Set<String> paths = new TreeSet<String>();
    public Object visit(Element element) {
        final IPath parentPath = (IPath) peek();
        final IPath path = parentPath.append(element.getLabel());
        if (!hasChildren(element))
            paths.add(path);
        return path;
    }
}