c# - 如何动态地将条件和方法传递给递归方法

Question

我想做一个这样的方法，

public dynamic Traverse(dynamic entity, conditions, method)
{
    foreach (var propInfo in GetTraversableProperties(entity))
    {
        if (condition) method(propInfo.GetValue(etc));
        Traverse(propInfo, condition, method);
    }
    return entity;
}

我该怎么做？将条件和方法作为参数传递的语法是什么？另外，将条件作为方法并检查它的返回值是否更有意义？

Answer 1

您的方法和 Gary 的回答都是具体化对象图递归遍历的抽象概念的完全合理的方法。但是，我看到四个潜在问题。不知道您的确切情况，也许这些对您来说不是问题，或者您应该考虑它们:

首先，假设您正在遍历的图具有极长的路径。您正在隐式执行深度优先遍历，并且即使在支持尾递归的体系结构上也无法轻松使您的方法成为尾递归，因此您冒着调用堆栈耗尽的风险。

其次，你假设图是无环的；如果图形是循环的，那么您肯定会用完堆栈空间。

第三，我不明白为什么遍历算法会返回一个实体。为什么这个方法不是无效的？或者，如果您将返回用作累加器来累加遍历计算的值，那么为什么递归步骤不对返回的实体执行某些操作？

第四，这里的关注点分离似乎很糟糕。调用者负责确定 (1) 图的根是什么，(2) 如何处理每个节点。但是被调用者负责 (3) 找出要递归的对象。这对我来说似乎很奇怪。调用者提供起点；来电者不应该对如何继续进行有发言权吗？

我一般是这样解决这个问题的:

• 使用在堆上分配的显式堆栈而不是使用调用堆栈来控制流
• 跟踪我之前访问过的节点并且不再访问它们
• 让调用者确定对象何时具有可遍历的子对象。如果调用者希望遍历在基本情况下“触底”，则调用者可以返回一个空的子集。

如果我想要一个累加器，我可能会实现类似这个草图的东西:

static R DepthFirstGraphAccumulate<T, R>(
    T root, 
    Func<T, IEnumerable<T>> children, 
    Func<T, R, R> accumulate)
{
    var accumulator = default(R);
    var visited = new HashSet<T>();
    var stack = new Stack<T>;
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        if (!visited.Contains(current))
        {
            visited.Add(current);
            foreach(var child in children(current))
                stack.Push(child);
            accumulator = accumulate(current, accumulator);
        }
    }
    return accumulator;
}

因此，例如，如果我有一个整数图并且我希望对从特定起始节点可到达的节点求和，我会说:

int total = DepthFirstGraphAccumulate<Node, int>(
    startNode, 
    node=>node.NeighbouringNodes, 
    (node, sum)=>node.Value + sum);

但是，我很想在“让我们分离关注点”的道路上更进一步，然后说，嘿，让我们写一个抽象的遍历器吧:

static IEnumerable<T> DepthFirstGraphTraversal<T>(
    T root, 
    Func<T, IEnumerable<T>> children)
{
    var visited = new HashSet<T>();
    var stack = new Stack<T>;
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        if (!visited.Contains(current))
        {
            visited.Add(current);
            foreach(var child in children(current))
                stack.Push(child);
            yield return current;
        }
    }
}

现在如果我想对图中的每个节点执行一些操作，我只需说:

foreach(var node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes))
     DoSomething(node);

如果我想表达“对每个符合条件的节点做某事”的概念，那么我会写:

var nodes = from node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes)
            where condition(node)
            select node;
foreach(var matchingNode in nodes) DoSomething(matchingNode);