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

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

你的方法和加里的答案都是具体化对象图递归遍历的抽象概念的完全合理的方法。然而，我看到了四个潜在的问题。不知道您的确切场景，也许这些对您来说不是问题，或者也许您应该考虑它们：

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

其次，您假设该图是非循环的；如果图表是循环的，那么您肯定会耗尽堆栈空间。

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

第四，你的关注点分离似乎很糟糕。调用者负责确定（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);

Answer 2

我认为使用 Func 委托来满足条件是有意义的。至于如何传递方法，这又会用到委托。我会做类似的事情：

public dynamic Traverse(dynamic entity, Func<dynamic, bool> conditions, Action<dynamic> method)
{
    foreach (var propInfo in GetTraversableProperties(entity))
    {
        if (conditions(entity)) method(propInfo.GetValue(etc));
        Traverse(propInfo, conditions, method);
    }
    return entity;
}

Func: http://msdn.microsoft.com/en -us/library/bb549151.aspx

操作：http://msdn.microsoft.com/en-us/library/018hxwa8.aspx