使用具有可赋值Func委托的对象的基于树的数学表达式

Question

我想在C#中实现一个通用的树数据结构,它有一个类Tree<E>,它引用一个根TreeNode<E>对象,该对象包含一个子链接列表和一个相同节点类型的单个父节点.这是一个基本的树结构,我实际上没有任何问题.

我想扩展这个树结构来创建Function,它扩展Tree<double>,以及Expression适当扩展的赞美节点类型TreeNode<double>.我想用这个结构来表示可以用函数的适当变量计算的数学函数.

我目前正处于这个项目的设计阶段,所以有很多方法可以实现这个,但我正在寻找具有适当抽象级别的设计来覆盖所有类型的功能,同时仍保持其参数签名气密性.例如,我应该能够Function为数学函数创建一个运行时:

f() = 42,f(x) = x^2,f(x, y) = x/y + 5,等.

如果每个Expression都有自己的子列表(子表达式分解以定义给定其参数的函数的过程),那么Expression应该使用某种评估方法,该方法接受double值并吐出它们的标量值(或者如果可能的话,将其提取到Vector级别).

我对LINQ这样的函数式语言不太熟悉,但如果有的话,是否会有一种简单而有效的方法来实现我正在计划使用的东西？如果我不必为每种基本操作(例如SinExpression(X)或者AdditionExpression(X,Y)一些)创建具体的类,那就太棒了,但是能够动态地定义可能存储在Dictionary中的数学函数,并提供所有变量要么是其他表达式,要么归结为浮点值.那时,具体的函数类可以扩展这些抽象的函数类,如果我只需要在基础构造函数中定义评估函数.

我还要注意,维护树结构很重要,因为我计划在单独的程序中使用这些表达式,这将直接更改函数的表达式树(更改节点,删除分支等).

任何人都能指出我正确的方向吗？我将不胜感激.

Answer 1

已经有一个API将复杂的操作表示为节点树; LINQ ExpressionAPI.对于一个简单的例子,您可以让编译器为您构建树 - 例如:

Expression<Func<double,double,double>> f = (x,y) => Math.Sin(x/y) + 5;

这可用于通过调用来评估事物Compile(),即

var func = f.Compile(); // this is a Func<double,double,double>
Console.WriteLine(func(12,5));
Console.WriteLine(func(23,4));

但表达式树更复杂,可以任意检查.此外,您可以使用ExpressionVisitor交换件.例如,假设我们想将"x"替换为"ln(x)"作为随机基因突变的一部分:

// swap x for ln(x)
var munged = SwapExpressionVisitor.Swap(
    f, // the lambda to rewrite
    f.Parameters[0], // "x"
    Expression.Call(typeof(Math), "Log", null, f.Parameters[0]) // ln(x)
); // (x, y) => (Sin((Log(x) / y)) + 5)

func = munged.Compile();
Console.WriteLine(func(12, 5));
Console.WriteLine(func(23, 4));

使用如下实用程序:

class SwapExpressionVisitor : ExpressionVisitor
{
    public static Expression<T> Swap<T>(Expression<T> lambda,
        Expression from, Expression to)
    {
        return Expression.Lambda<T>(
            Swap(lambda.Body, from, to), lambda.Parameters);
    }
    public static Expression Swap(
        Expression body, Expression from, Expression to)
    {
        return new SwapExpressionVisitor(from, to).Visit(body);
    }
    private readonly Expression from, to;
    public SwapExpressionVisitor(Expression from, Expression to)
    {
        this.from = from;
        this.to = to;
    }
    public override Expression Visit(Expression node)
    {
        return node == from ? to : base.Visit(node);
    }
}