Logical operator on array of functions

Question

I've had this idea for a while, and I'm curious if it's possible to implement in a worthwhile way. I want to take an array of boolean-returning lambda expressions and perform logical operations on their results. Here's a pointless example of a valid list:

var tests = new List<Func<int, bool>>() {
    (x) => x > 10,
    (x) => x < 100,
    (x) => x != 42
};

What I'd like to do is essentially

bool result = tests.And();

or perform other logical operations. I realize I could write an IEnumerable-implementing class and do this, but I was wondering if it has already been done. Obviously, the implementation has to work efficiently, short-circuiting in the same way as

if (truthyExpression || falseyExpression)

would never get around to evaluating falseyExpression.

The only thing I see in the framework that could maybe be helpful is Bit Array, but I'm not sure how I could use that without pre-evaluating every expression, defeating the usefulness of short-cicuiting.

Answer 1

You could use the built-in Enumerable.Any and Enumerable.All extension methods.

bool andResult = tests.All(test => test(value));
bool orResult = tests.Any(test => test(value));

Answer 2

Sure you could.

The easy way

var tests = new List<Func<int, bool>>() {
    (x) => x > 10,
    (x) => x < 100,
    (x) => x != 42
};

We 're going to aggregate all these predicates into one by incrementally logical-and-ing each one with the already existing result. Since we need to start somewhere, we 'll start with x => true because that predicate is neutral when doing AND (start with x => false if you OR):

var seed = (Func<int, bool>)(x => true);
var allTogether = tests.Aggregate(
    seed,
    (combined, expr) => (Func<int, bool>)(x => combined(x) && expr(x)));

Console.WriteLine(allTogether.Invoke(30)); // True

That was easy! It does have a few limitations though:

• it only works on objects (as does your example)
• it might be a tiny bit inefficient when your list of predicates gets large (all those function calls)

The hard way (using expression trees instead of compiled lambdas)

This will work everywhere (e.g. you can also use it to pass predicates to SQL providers such as Entity Framework) and it will also give a more "compact" final result in any case. But it's going to be much harder to make it work. Let's get to it.

First, change your input to be expression trees. This is trivial because the compiler does all the work for you:

var tests = new List<Expression<Func<int, bool>>>() {
    (x) => x > 10,
    (x) => x < 100,
    (x) => x != 42
};

Then aggregate the bodies of these expressions into one, the same idea as before. Unfortunately, this is not trivial and it is not going to work all the way, but bear with me:

var seed = (Expression<Func<int, bool>>)
    Expression.Lambda(Expression.Constant(true), 
    Expression.Parameter(typeof(int), "x"));

var allTogether = tests.Aggregate(
    seed,
    (combined, expr) => (Expression<Func<int, bool>>)
        Expression.Lambda(
        Expression.And(combined.Body, expr.Body), 
        expr.Parameters
    ));

Now what we did here was build one giant BinaryExpression expression from all the individual predicates.

You can now pass the result to EF or tell the compiler to turn this into code for you and run it, and you get short-circuiting for free:

Console.WriteLine(allTogether.Compile().Invoke(30)); // should be "true"

Unfortunately, this final step won't work for esoteric technical reasons.

But why won't it work?

Because allTogether represents an expression tree that goes somewhat like this:

FUNCTION 
  PARAMETERS: PARAM(x)
  BODY:  AND +-- NOT-EQUAL +---> PARAM(x)
          |             \---> CONSTANT(42)
          |
         AND +-- LESS-THAN +---> PARAM(x)
             |             \---> CONSTANT(100)
             |
            AND +-- GREATER-THAN +---> PARAM(x)
             |                   \---> CONSTANT(10)
             |
            TRUE

Each node in the above tree represents an Expression object in the expression tree to be compiled. The catch is that all 4 of those PARAM(x) nodes, while logically identical are in fact different instances (that help the compiler gave us by creating expression trees automatically? well, each one naturally has their own parameter instance), while for the end result to work they must be the same instance. I know this because it has bitten me in the past.

So, what needs to be done here is that you then iterate over the resulting expression tree, find each occurrence of a ParameterExpression and replace each an every one of them with the same instance. That same instance will also be the second argument used when constructing seed.

Showing how to do this will make this answer way longer than it has any right to be, but let's do it anyway. I 'm not going to comment very much, you should recognize what's going on here:

class Visitor : ExpressionVisitor
{
    private Expression param;

    public Visitor(Expression param)
    {
        this.param = param;
    }

    protected override Expression VisitParameter(ParameterExpression node)
    {
        return param;
    }
}

And then:

var param = Expression.Parameter(typeof(int), "x");
var seed = (Expression<Func<int, bool>>)
    Expression.Lambda(Expression.Constant(true), 
    param);
var visitor = new Visitor(param);

var allTogether = tests.Aggregate(
    seed,
    (combined, expr) => (Expression<Func<int, bool>>)
        Expression.Lambda(
        Expression.And(combined.Body, expr.Body), 
        param
    ),
    lambda => (Expression<Func<int, bool>>)
        // replacing all ParameterExpressions with same instance happens here
        Expression.Lambda(visitor.Visit(lambda.Body), param)
    );

Console.WriteLine(allTogether.Compile().Invoke(30)); // "True" -- works! 

Answer 3

In order to turn a sequence of Func<int, bool> objects into a bool you're going to need to have an integer to apply to each value. If you already know what that integer is, then you can do what Julien describes:

bool andResult = tests.All(test => test(value));
bool orResult = tests.Any(test => test(value));

If you don't, then what you want to do is create a Func<int, bool> from the sequence of booleans, rather than a bool:

Func<int, bool> andResult = value => tests.All(test => test(value));
Func<int, bool> orResult = value => tests.Any(test => test(value));

We can easily generalize this into a generic function:

public static Func<T, bool> And<T>(this IEnumerable<Func<T, bool>> predicates)
{
    return value => predicates.All(p => p(value));
}
public static Func<T, bool> Or<T>(this IEnumerable<Func<T, bool>> predicates)
{
    return value => predicates.Any(p => p(value));
}

which allows you to write:

Func<int, bool> result = tests.And();

Answer 4

How about this?

using System;
using System.Collections.Generic;
using System.Linq;
namespace SO7
{
    class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            LogicList<int> intBasedLogicalList = new LogicList<int>(new Func<int, bool>[] {x => x<3, x => x <5, x => x<8});
            Console.WriteLine(intBasedLogicalList.And(2));
            Console.WriteLine(intBasedLogicalList.And(4));
            Console.WriteLine(intBasedLogicalList.Or(7));
            Console.WriteLine(intBasedLogicalList.Or(8));

            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
        }
    }

    public class LogicList<T> : List<Func<T, bool>>
    {

        private List<Func<T,bool>> _tests;

        public LogicList(IEnumerable<Func<T, bool>> tests)
        {
            _tests = new List<Func<T, bool>>();
            foreach(var test in tests)
            {
                _tests.Add(test);
            }
        }

        public bool And(T argument){
            foreach(var test in _tests)
            {
                if (!test(argument)){
                    return false;
                }
            }
            return true;
        }

        public bool Or(T argument){
            return _tests.Any(x => x(argument));

        }

    }

}