Predicates are sets
A predicate is a function that takes a value and computes a true or false response.
This type can be expressed easily in .NET. In C#, the
Predicate<T> Delegate
is declared as
public delegate bool Predicate<in T>(T obj)A set is an abstract data type that stores values, in no particular order, without repetitions.
.NET defines many interfaces for sets:
System.Collections.Generic.ISet<T>, a generic mutable finite setSystem.Collections.Immutable.IImmutableSet<T>, a generic immutable finite setMicrosoft.SqlServer.Management.Sdk.Sfc.IReadonlySet, an immutable non-generic finite set, for some reason in theMicrosoft.SqlServernamespace.
All of these types have a Contains method, which can be cast to Predicate<T>. This means that any of the set types in .NET can be used as predicates! Intuitively, this predicate answers the question “does this set contain the argument?”
Is the converse also true? Can we create a set from predicates? Let’s declare a PredicateSet in C# 6:
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Collections.Generic;
using System.Linq;
public partial class PredicateSet<T> {
private readonly Predicate<T> indicator;
public PredicateSet(Predicate<T> indicator) {
this.indicator = indicator;
}
public bool Contains(T item) => indicator(item);
}
namespace Test {
[TestClass]
public partial class PredicateSetTest {
[TestMethod]
public void ItemTest() {
var ps = new PredicateSet<int>(i => i == 2);
Assert.IsFalse(ps.Contains(0));
Assert.IsTrue(ps.Contains(2));
Assert.IsFalse(ps.Contains(100));
}
}
}That looks sort of like a set. It seems like we can define more interesting sets already, too:
namespace Test {
partial class PredicateSetTest {
[TestMethod]
public void OddsTest() {
var odds = new PredicateSet<int>(i => (i & 1) == 1);
Assert.IsFalse(odds.Contains(0));
Assert.IsTrue(odds.Contains(1));
Assert.IsFalse(odds.Contains(2));
Assert.IsTrue(odds.Contains(3));
Assert.IsFalse(odds.Contains(-157204));
Assert.IsTrue(odds.Contains(-157203));
Assert.IsFalse(odds.Contains(65432));
Assert.IsTrue(odds.Contains(65431));
}
private static readonly Random Random = new Random();
/// It takes too long to run our tests on all the integers,
/// so let's just try some random ones
private static IEnumerable<int> SomeIntegers() {
yield return int.MinValue;
yield return int.MinValue + 1;
yield return int.MaxValue;
yield return int.MaxValue - 1;
foreach (var i in Enumerable.Range(100, 200)) {
yield return i;
}
foreach (var i in Enumerable.Range(1, 32768)) {
yield return Random.Next(int.MinValue, int.MaxValue);
}
}
[TestMethod]
public void SpecialSets() {
var empty = new PredicateSet<int>(i => false);
var universal = new PredicateSet<int>(i => true);
foreach (var i in SomeIntegers()) {
Assert.IsTrue(universal.Contains(i));
Assert.IsFalse(empty.Contains(i));
}
}
}
}It’s a neat trick. Can we add set algebra?
public partial class PredicateSet<T> {
public PredicateSet<T> Union(PredicateSet<T> other) =>
new PredicateSet<T>(
v => this.indicator(v) || other.indicator(v));
public PredicateSet<T> Intersection(PredicateSet<T> other) =>
new PredicateSet<T>(
v => this.indicator(v) && other.indicator(v));
public PredicateSet<T> Complement() =>
new PredicateSet<T>(
v => !this.indicator(v));
}
namespace Test {
partial class PredicateSetTest {
[TestMethod]
public void UnionTest() {
var a = new PredicateSet<int>(i => i == 3);
var b = new PredicateSet<int>(i => i > 5 && i < 8);
var u1 = a.Union(b);
var u2 = b.Union(a); // assert commutivity
foreach (var u in new[] { u1, u2 }) {
Assert.IsFalse(u.Contains(2));
Assert.IsTrue(u.Contains(3));
Assert.IsFalse(u.Contains(4));
Assert.IsFalse(u.Contains(5));
Assert.IsTrue(u.Contains(6));
Assert.IsTrue(u.Contains(7));
Assert.IsFalse(u.Contains(8));
}
}
[TestMethod]
public void IntersectionTest() {
var odd = new PredicateSet<int>(i => (i & 1) == 1);
var b = new PredicateSet<int>(i => i > 5 && i < 8);
var i1 = odd.Intersection(b);
var i2 = b.Intersection(odd); // assert commutivity
foreach (var u in new[] { i1, i2 }) {
foreach (var i in SomeIntegers()) {
bool shouldContain = (i == 7);
Assert.AreEqual(shouldContain, i1.Contains(i));
Assert.AreEqual(shouldContain, i2.Contains(i));
}
}
}
[TestMethod]
public void ComplementTest() {
var odds = new PredicateSet<int>(i => (i & 1) == 1);
var evens = odds.Complement();
foreach (var i in SomeIntegers()) {
Assert.AreNotEqual(odds.Contains(i), evens.Contains(i));
}
}
}
}Well, that’s a very powerful way to define sets. Why isn’t it used more?
Unfortunately, PredicateSet can’t implement any of the existing interfaces for sets. They all want to be IEnumerable<T>. There’s no way for a PredicateSet to be able to generate all of the elements that are contained in it, or even count them.
Predicate<string> isUpper = s => s.ToUpper() == s;
var allUppercaseStrings = new PredicateSet<string>(isUpper);
allUppercaseStrings.Count(); // ???
for (string s in allUppercaseStrings) {
// ???
}Similarly, set relations like Subset, Superset, and Equals are impossible to calculate.
Here’s the entire combined source listing for the PredicateSet class:
PredicateSet.cs
using System;
public partial class PredicateSet<T> {
private readonly Predicate<T> indicator;
public PredicateSet(Predicate<T> indicator) {
this.indicator = indicator;
}
public bool Contains(T item) => indicator(item);
public PredicateSet<T> Union(PredicateSet<T> other) =>
new PredicateSet<T>(
v => this.indicator(v) || other.indicator(v));
public PredicateSet<T> Intersection(PredicateSet<T> other) =>
new PredicateSet<T>(
v => this.indicator(v) && other.indicator(v));
public PredicateSet<T> Complement() =>
new PredicateSet<T>(
v => !this.indicator(v));
}Isn’t that interesting? Set algebra and Boolean algebra seem to be incredibly closely related.