Most efficient way to test equality of lambda expressions

Hmmm... I guess you'd have to parse the tree, checking the node-type and member of each. I'll knock up an example...

using System;
using System.Linq.Expressions;
class Test {
    public string Foo { get; set; }
    public string Bar { get; set; }
    static void Main()
    {
        bool test1 = FuncTest<Test>.FuncEqual(x => x.Bar, y => y.Bar),
            test2 = FuncTest<Test>.FuncEqual(x => x.Foo, y => y.Bar);
    }

}
// this only exists to make it easier to call, i.e. so that I can use FuncTest<T> with
// generic-type-inference; if you use the doubly-generic method, you need to specify
// both arguments, which is a pain...
static class FuncTest<TSource>
{
    public static bool FuncEqual<TValue>(
        Expression<Func<TSource, TValue>> x,
        Expression<Func<TSource, TValue>> y)
    {
        return FuncTest.FuncEqual<TSource, TValue>(x, y);
    }
}
static class FuncTest {
    public static bool FuncEqual<TSource, TValue>(
        Expression<Func<TSource,TValue>> x,
        Expression<Func<TSource,TValue>> y)
    {
        return ExpressionEqual(x, y);
    }
    private static bool ExpressionEqual(Expression x, Expression y)
    {
        // deal with the simple cases first...
        if (ReferenceEquals(x, y)) return true;
        if (x == null || y == null) return false;
        if (   x.NodeType != y.NodeType
            || x.Type != y.Type ) return false;

        switch (x.NodeType)
        {
            case ExpressionType.Lambda:
                return ExpressionEqual(((LambdaExpression)x).Body, ((LambdaExpression)y).Body);
            case ExpressionType.MemberAccess:
                MemberExpression mex = (MemberExpression)x, mey = (MemberExpression)y;
                return mex.Member == mey.Member; // should really test down-stream expression
            default:
                throw new NotImplementedException(x.NodeType.ToString());
        }
    }
}

I think most efficiency out of Lambdas you getting when you will use lambda-efficient collection - what I mean is column-based collection that can be enumerated by only one or more selected columns achieving this by implementing IEnumerable on each column separately - let's call it first step ;)

That is only my idea that I want to do some day. I have no clues at the moment but I think many will agree with me that enumerating to check value through single variables list in compare to checking some property in list of objects is like proving itself.

Next second step to get more from functional programming: use as a collections representing columns use sorted-list, hash-table or any other search-efficient collection.

class LambdaReadyColumn<int> : HashTable<int> 

And another third step connect items between columns with some pointers so instead of keeping under-hood columns in:

class LambdaReadyColumn<int> : IEnumabrable<int> 

keep data in something closer to:

class LambdaReadyColumn<LambdaReadyColumnItem<T, int>> : IEnumabrable<int> 
//with example constructor like: 
public LambdaReadyColumn<LambdaReadyColumnItem<T, int>>(Hash, LambdaReadyColumnItem, LambdaReadyColumnItem, T, int); 

where:

• CollectionItem - references to right and left column items of same T item
• Hash - to make search faster
• int - type representing column
• T - fourth step whole LambdaReadyCollection in column collection easily understanding simply to make Select(T) at the returning item descriptor faster but also avoiding traversing few references left/right for items with many properties.

Finally with all the step we have collection with double data: row-based and collection based additionally lot of reference data. Of course row-based HashTable can keep data and column-based only references but than building every collection to return from the statement would use lot of referencing.

To achieve it you need to use reflections, dynamic types or other advanced technique depending on the language.