How do I compose Linq Expressions? ie Func<Exp<Func<X, Y>>, Exp<Func<Y, Z>>, Exp<Func<X, Z>>>

Question

I'm creating a Validator<T> class. I'm attempting to implement the Linq SelectMany extension methods for my validator to be able to compose expressions using a Linq query and validate the final result even when the underlying values change.

The following test code demonstrates my intent.

var a = 2;
var b = 3;

var va = Validator.Create(() => a, n => n >= 0 && n < 5);
var vb = Validator.Create(() => b, n => n >= 0 && n < 5);

var vc = from ia in va
         from ib in vb
         select ia + ib;

Debug.Assert(vc.Value == a + b); //2 + 3
Debug.Assert(vc.Value == 5);

Debug.Assert(vc.IsValid == true);

a = 7;

Debug.Assert(vc.Value == a + b); //7 + 3
Debug.Assert(vc.Value == 10);

Debug.Assert(va.IsValid == false);
Debug.Assert(vb.IsValid == true);
Debug.Assert(vc.IsValid == false);

I've seen the following question How do I compose existing Linq Expressions which shows me how to compose two Func<T, bool>'s together using an And expression, but I need to be able to compose functions together in a more, well, functional way.

I have, for example, the following two expressions:

public Expression<Func<T>> ValueExpression { get; private set; }
public Expression<Func<T, bool>> ValidationExpression { get; private set; }

I wish to create a new expression like this:

    public Expression<Func<bool>> IsValidExpression
    {
        get
        {
            // TODO: Compose expressions rather than compile & invoke.
        }
    }

More succinctly I'm trying to create these functions:

// Specific case
Func<Expression<Func<T>>, Expression<Func<T, bool>>, Expression<Func<bool>>>
// General case
Func<Expression<Func<X, Y>>, Expression<Func<Y, Z>>, Expression<Func<X, Z>>>

The general case function can be modified to accept different numbers of generic arguments as needed to compose any function.

I've searched Stack Overflow (of course) and the web, but haven't an example that solves this issue.

My code for the Validator<T> class is below.

public class Validator<T>
{
    public Validator(Expression<Func<T>> valueFunc,
        Expression<Func<T, bool>> validationFunc)
    {
        this.ValueExpression = valueFunc;
        this.ValidationExpression = validationFunc;
    }

    public Expression<Func<T>> ValueExpression { get; private set; }
    public Expression<Func<T, bool>> ValidationExpression { get; private set; }

    public T Value { get { return this.ValueExpression.Compile().Invoke(); } }

    public bool IsValid { get { return this.IsValidExpression.Compile().Invoke(); } }

    public Expression<Func<bool>> IsValidExpression
    {
        get
        {
            // TODO: Compose expressions.
        }
    }
}

My SelectMany extensions contain loads of yucky .Compile().Invoke() which I want to get rid of.

public static Validator<U> SelectMany<T, U>(this Validator<T> @this, Expression<Func<T, Validator<U>>> k)
{
    Expression<Func<T>> fvtv = @this.ValueExpression;
    Expression<Func<Validator<U>>> fvu = () => k.Compile().Invoke(fvtv.Compile().Invoke());
    Expression<Func<U>> fvuv = fvu.Compile().Invoke().ValueExpression;
    Expression<Func<U, bool>> fvtiv = u => @this.ValidationExpression.Compile().Invoke(fvtv.Compile().Invoke());
    return fvuv.ToValidator(fvtiv);
}

public static Validator<V> SelectMany<T, U, V>(this Validator<T> @this, Expression<Func<T, Validator<U>>> k, Expression<Func<T, U, V>> s)
{
    Expression<Func<Validator<U>>> fvu = () => @this.SelectMany(k);
    Expression<Func<T>> fvtv = @this.ValueExpression;
    Expression<Func<U>> fvuv = fvu.Compile().Invoke().ValueExpression;
    Expression<Func<T, bool>> fvtiv = @this.ValidationExpression;
    Expression<Func<U, bool>> fvuiv = u => fvu.Compile().Invoke().ValidationExpression.Compile().Invoke(u);
    Expression<Func<V>> fvv = () => s.Compile().Invoke(fvtv.Compile().Invoke(), fvuv.Compile().Invoke());
    Expression<Func<V, bool>> fvviv = v => fvtiv.Compile().Invoke(fvtv.Compile().Invoke()) && fvuiv.Compile().Invoke(fvuv.Compile().Invoke());
    return fvv.ToValidator(fvviv);
}

Thanks in advance!

Wiltshire

Really struggling to see what you mean by "in a more functional way". What would you need to do that you can't do by just removing all the Expression<> .Compile() and .Invoke()s? – Cogen

I'm curious as to why you would want to validate an expression to produce the value as opposed to simply validating an actual value. Can you elaborate on this point? – Porridge

Here's an example - I'm trying to compose functions such as f(x) = x + 1 & g(x) = sqrt(x) then h(x) = f(g(x)). Now if I have a constraint on g such that x >= 0 (sqrt of -ve numbers etc) then I want that constraint to propagate to the function h. When my underlying value of x changes I want to be able to ask the function h if I should consider its result as still valid. (This is a somewhat contrived example, but it should help to clarify.) Cheers. – Wiltshire

I think this stack-exchange proposal might be of interest to you. If it is show your support and help get it into beta. – Quoit

Answer 1

The equivalent of Haskell's function composition operator

(.) :: (b->c) -> (a->b) -> (a->c)
f . g = \ x -> f (g x)

would in C# probably be something like

static Expression<Func<A, C>> Compose<A, B, C>(
    Expression<Func<B, C>> f,
    Expression<Func<A, B>> g)
{
    var x = Expression.Parameter(typeof(A));
    return Expression.Lambda<Func<A, C>>(
        Expression.Invoke(f, Expression.Invoke(g, x)), x);
}

Is this what you're looking for?

Example:

Compose<int, int, string>(y => y.ToString(), x => x + 1).Compile()(10); // "11"

Apanage

That looks pretty much like what I was after. Cheers. Now I can get on with my next head-ache. Monads are crazy! – Wiltshire

We have a whole set of such operators in our internal lib. It's a shame Microsoft doesn't include stuff to make the Expression<Func<..>> really awesome (relatively speaking) – Dentoid

Answer 2

While dtb's answer works for several scenarios, it is suboptimal as such an expression cannot be used in Entity Framework, as it cannot handle Invoke calls. Unfortunately, to avoid those calls one needs a lot more code, including a new ExpressionVisitor derived class:

static Expression<Func<A, C>> Compose<A, B, C>(Expression<Func<B, C>> f,
                                               Expression<Func<A, B>> g)
{
    var ex = ReplaceExpressions(f.Body, f.Parameters[0], g.Body);

    return Expression.Lambda<Func<A, C>>(ex, g.Parameters[0]);
}

static TExpr ReplaceExpressions<TExpr>(TExpr expression,
                                       Expression orig,
                                       Expression replacement)
    where TExpr : Expression 
{
    var replacer = new ExpressionReplacer(orig, replacement);

    return replacer.VisitAndConvert(expression, nameof(ReplaceExpressions));
}

private class ExpressionReplacer : ExpressionVisitor
{
    private readonly Expression From;
    private readonly Expression To;

    public ExpressionReplacer(Expression from, Expression to)
    {
        From = from;
        To = to;
    }

    public override Expression Visit(Expression node)
    {
        return node == From ? To : base.Visit(node);
    }
}

This replaces every instance of the first parameter in the first expression with the expression in the second expression. So a call like this:

Compose((Class1 c) => c.StringProperty, (Class2 c2) => c2.Class1Property

Would yield the expression (Class2 c2) => c2.Class1Property.StringProperty.

Alard

As a sidenote, this is valid only if "f" and "g" are pure functions. If you're using this for Entity framework, chances are they already are anyway. Otherwise, you might run into problems with side effects. – Interactive