Filtering with truth tables

问题:

Imagine a Person class with a boolean flag indicating whether or not the person is employable - set to false by default.

public class Person{
    boolean employable = false;
    ...
}

Now imagine having some external boolean methods which act on Person objects. For example, consider static boolean methods in a utility class.

public class PersonUtil{
    public static boolean ofWorkingAge(Person p){
        if(p.getAge() > 16) return true;
        return false;
    }
    ...
}

Boolean static methods are in essence analogous to boolean valued functions i.e. predicates.

We can construct a 2^(#predicates)-by-#predicates truth table out of predicates. For example, given three predicates: ofWorkingAge, ofGoodCharacter, isQualified we can construct the following 8-by-3 truth table:

T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F

We now want to employ people with desirable qualities. Let + indicate that we wish to consider somebody employable (i.e. set their employability flag to true) and - the opposite.

T T T | +
T T F | +
T F T | +
T F F | -
F T T | +
F T F | -
F F T | -
F F F | -

Now imagine having a collection of Person objects. For each person we adjust their employability flag according to the three predicates. We also update a count (this forces us to use the entire truth table instead of just the positives), so that given 1,000 people we want to end up with something like:

T T T | +   100
T T F | +   200
T F T | +   50
T F F | -   450
F T T | +   50
F T F | -   50
F F T | -   50
F F F | -   50

Presumably this can be thought of as filtering with truth tables. Setting employability flags and updating counts is a rather contrived example but you can easily see how we might instead want to set and update much more complicated things.

QUESTION

Is there a way of elegantly doing this? I can think of two solutions:

Clunky solution

Have a giant hand coded if, else if, else chain.

if(ofWorkingAge && ofGoodCharacter && isQualified){
    c1++;
    p.setEmployable(true)
}
else if(ofWorkingAge && ofGoodCharacter && !isQualified){
    c2++;
    p.setEmployable(true)
}
...
else if(!ofWorkingAge && !ofGoodCharacter && isQualified){
    c7++;
}
else{
    c8++;
}

This is just bad.

Slightly smarter solution

Pass predicates (perhaps in an array) and a collection of sentences to a method. Let the method generate the corresponding truth table. Loop over the people, set their employability, and return an array of counts.

I can see how things could be done with functional interfaces. This SO answer is potentially relevant. You could change PrintCommand to IsQualified and pass callCommand a Person instead of a string. But this also seems kindah clunky because we'd then have to have a new interface file for every predicate we come up with.

Is there any other Java 8-ish way of doing this?

回答1:

Let's start with the list of predicates you have:

List<Predicate<Person>> predicates = Arrays.<Predicate<Person>> asList(
        PersonUtil::ofWorkingAge, PersonUtil::ofGoodCharacter,
        PersonUtil::isQualified);

To track which predicate is true or false, let's attach names to them creating NamedPredicate class:

public static class NamedPredicate<T> implements Predicate<T> {
    final Predicate<T> predicate;
    final String name;

    public NamedPredicate(Predicate<T> predicate, String name) {
        this.predicate = predicate;
        this.name = name;
    }

    @Override
    public String toString() {
        return name;
    }

    @Override
    public boolean test(T t) {
        return predicate.test(t);
    }
}

(one may attach BitSet or something like this for efficiency, but String names are also fine).

Now we need to generate a truth table which is a new list of predicates having names like "T T F" and able to apply the given combination of source predicates, negated or not. This can be generated easily with a bit of functional programming magic:

Supplier<Stream<NamedPredicate<Person>>> truthTable
    = predicates.stream() // start with plain predicates
        .<Supplier<Stream<NamedPredicate<Person>>>>map(
            // generate a supplier which creates a stream of 
            // true-predicate and false-predicate
            p -> () -> Stream.of(
                    new NamedPredicate<>(p, "T"),
                    new NamedPredicate<>(p.negate(), "F")))
        .reduce(
            // reduce each pair of suppliers to the single supplier
            // which produces a Cartesian product stream
            (s1, s2) -> () -> s1.get().flatMap(np1 -> s2.get()
                            .map(np2 -> new NamedPredicate<>(np1.and(np2), np1+" "+np2))))
        // no input predicates? Fine, produce empty stream then
        .orElse(Stream::empty);

as truthTable is a Supplier<Stream>, you can reuse it as many times as you want. Also note that all the NamedPredicate objects are generated on the fly by demand, we don't store them anywhere. Let's try to use this supplier:

truthTable.get().forEach(System.out::println);

The output is:

T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F

Now you can classify the persons collection by the truth table, for example, in the following way:

Map<String,List<Person>> map = truthTable.get().collect(
    Collectors.toMap(np -> np.toString(), // Key is string like "T T F"
        // Value is the list of persons for which given combination is true
        np -> persons.stream().filter(np).collect(Collectors.toList()),
        // Merge function: actually should never happen; 
        // you may throw assertion error here instead
        (a, b) -> a,
        // Use LinkedHashMap to preserve an order
        LinkedHashMap::new));

Now you can easily get the counts:

map.forEach((k, v) -> System.out.println(k+" | "+v.size()));

To update the employable field we need to know how the desired truth table is specified. Let it be the collection of truth strings like this:

Collection<String> desired = Arrays.asList("T T T", "T T F", "T F T", "F T T");

In this case you may use the previously generated map:

desired.stream()
       .flatMap(k -> map.get(k).stream())
       .forEach(person -> person.setEmployable(true));

回答2:

Basically, a truth value is a single bit and you can always use an integer value of n bits to encode n truth value. Then, interpreting the integer value as a number allows you to associate values with the combination of truth values using a linear table.

So using an int a encoded truth value/ table index, a generic truth table class may look like this:

public class TruthTable<O,V> {
    final List<? extends Predicate<? super O>> predicates;
    final ArrayList<V> values;

    @SafeVarargs
    public TruthTable(Predicate<? super O>... predicates) {
        int size=predicates.length;
        if(size==0 || size>31) throw new UnsupportedOperationException();
        this.predicates=Arrays.stream(predicates)
            .map(Objects::requireNonNull).collect(Collectors.toList());
        values=new ArrayList<>(Collections.nCopies(1<<size, null));
    }
    public V get(O testable) {
        return values.get(index(testable, predicates));
    }
    public V get(boolean... constant) {
        if(constant.length!=predicates.size())
            throw new IllegalArgumentException();
        return values.get(index(constant));
    }
    public V set(V value, boolean... constant) {
        if(constant.length!=predicates.size())
            throw new IllegalArgumentException();
        return values.set(index(constant), value);
    }

    public static <T> int index(T object, List<? extends Predicate<? super T>> p) {
        int size=p.size();
        if(size==0 || size>31) throw new UnsupportedOperationException();
        return IntStream.range(0, size).map(i->p.get(i).test(object)? 1<<i: 0)
            .reduce((a,b) -> a|b).getAsInt();
    }
    public static <T> int index(boolean... values) {
        int size=values.length;
        if(size==0 || size>31) throw new UnsupportedOperationException();
        return IntStream.range(0, size).map(i->values[i]? 1<<i: 0)
            .reduce((a,b) -> a|b).getAsInt();
    }
}

The key point is the calculation of the int index from truth values. There are two versions. First, calculate from explicit boolean values for initializing the table or querying its state, second, for an actual test object and the list of applicable predicates. Note that these two methods are factored out into public static methods so that they can be used for alternative table types, e.g. an array of primitive values. The only thing to do is to create a linear storage for 2ⁿ values when you have n predicates, e.g. new int[1<<n] and then using these index methods for determining the entry to access for given values or an actual test candidate.

Instances of the generic TruthTable can be used as follows:

TruthTable<Person,Integer> scoreTable=new TruthTable<>(
    PersonUtil::ofWorkingAge, PersonUtil::ofGoodCharacter, PersonUtil::isQualified);
scoreTable.set(+100, true, true, true);
scoreTable.set(+200, true, true, false);
scoreTable.set(+50, true, false, true);
scoreTable.set(-450, true, false, false);
scoreTable.set(+50, false, true, true);
scoreTable.set(-50, false, true, false);
scoreTable.set(-50, false, false, true);
scoreTable.set(-50, false, false, false);

Person p = …
int score = scoreTable.get(p);

回答3:

I'm not sure if this is what you're looking for, but you could use a bitwise operators on your variables..

if(ofWorkingAge && ofGoodCharacter && isQualified){
c1++;
p.setEmployable(true)
}

might become

int combined = 0b00000000;
combined |= ofWorkingAge ? 0b00000100 : 0b00000000;
combined |= ofGoodCharacter ? 0b00000010 : 0b00000000;
combined |= isQualified ? 0b00000001 : 0b00000000;

switch (combined){
 case 0b00000111: 
    c1++;
    p.setEmployable(true)
    break;
 case 0b00000110: 
    // etc

where the last bits represent ofWorkingAge/ofGoodCharacter/isQualified.