Filterer Pattern

Disclaimer: What I am writing about here is my own idea, but it is quite likely that someone has already come up with it and described it (I was unable to find it, however). If so, please let me know, and I will reference it here.

Abstract

The Filterer pattern is a design pattern for Java (and potentially other OO languages with use-site variance only) that helps container-like objects return filtered versions of themselves.

Problem

Example

Container-Like Object

Let us start with a simple contained type (Item) and container type (Group):

interface Item {
    String name();
}

interface Group {
    List<? extends Item> items();
}

Note that Group makes use of covariance (? extends Item).

Filtering in Group

Now, I wanted Group to have a method that would return a version of itself but filtered by Items, so I added a filtered method:

interface Group {
    List<? extends Item> items();

    Group filtered(Predicate<? super Item> predicate);
}

Note that here we needed contravariance (? super Item).

Subinterface of Group

Such interface may look fine, but the problem with this design is that it is not versatile for subtypes of Item and Group:

interface ScoredItem extends Item {
    int score();
}

interface ScoredGroup extends Group {
    @Override
    List<? extends ScoreItem> items();

    @Override
    ScoredGroup filtered(Predicate<? super Item> predicate);
}

As you can see, we overrode filtered, but the parameter type (Predicate<? super Item>) had to remain unchanged. Because of type erasure in Predicate, we cannot overload this method either.

As a result, we are able to create a filtered ScoredGroup but unable to filter by ScoredItems (which makes filtered method much less useful).

Better Filtering in Subinterfaces

To mitigate this, we could add an extra method with a proper lower bound in Predicate (e.g. scoreFiltered):

interface ScoredGroup extends Group {
    @Override
    List<? extends ScoreItem> items();

    ScoredGroup scoreFiltered(Predicate<? super ScoredItem> predicate);

    @Override
    default ScoredGroup filtered(Predicate<? super Item> predicate) {
        return scoreFiltered(predicate);
    }
}

Impracticality of Better Filtering in Subinterfaces

But as soon as we add further subinterfaces (e.g. ScoreExplanatoryItem and ScoreExplanatoryGroup), it gets totally out of hand:

interface ScoreExplanatoryItem extends ScoredItem {
    String explanation();
}

interface ScoreExplanatoryGroup extends ScoredGroup {
    @Override
    List<? extends ScoreExplanatoryItem> items();

    ScoreExplanatoryGroup scoreExplanatoryFiltered(Predicate<? super ScoreExplanatoryItem> predicate);

    @Override
    default ScoreExplanatoryGroup scoreFiltered(Predicate<? super ScoredItem> predicate) {
        return scoreExplanatoryFiltered(predicate);
    }

    @Override
    default ScoreExplanatoryGroup filtered(Predicate<? super Item> predicate) {
        return scoreExplanatoryFiltered(predicate);
    }
}

Problem Summary

To sum up, since the filtered method cannot be overriden, we suffer from the following:

1. The subinterfaces of Group become cluttered, especially as we move down the type hierarchy.
2. The default methods in those subinterfaces are just boilerplate.
3. When accessing the subinterfaces, it may be difficult to decide which method to call to get the desired lower bound on Predicate.

Solution

What we need here is an ability to covariantly specify a lower bound of contravariant Predicate in the subinterfaces of Group.

In Java, it cannot be done explicitly (i.e. by overriding the filtered method with a different Predicate), but fortunately, it can be done by means of a helper interface, which I dubbed Filterer*.

* In case you wonder whether the word exists, consult Wiktionary.

Introducing Filterer

Interface

We define Filterer interface as follows:

@FunctionalInterface
interface Filterer<G extends Group, E extends Item> {
    G by(Predicate<? super E> predicate);
}

And thanks to this interface, we can redefine Group as follows:

interface Group {
    List<? extends Item> items();

    Filterer<?, ?> filtered();
}

Let's see how this works for the subinterfaces:

interface ScoredGroup extends Group {
    @Override
    List<? extends ScoreItem> items();

    @Override
    Filterer<? extends ScoredGroup, ? extends ScoredItem> filtered();
}

interface ScoreExplanatoryGroup extends ScoredGroup {
    @Override
    List<? extends ScoreExplanatoryItem> items();

    @Override
    Filterer<? extends ScoreExplanatoryGroup, ? extends ScoreExplanatoryItem> filtered();
}

As you can see, the interfaces remain clean (no extra methods, no boilerplate) because we are able to override filtered method now. And we do this by employing covariance (? extends) which sets the lower bound for the contravariant Predicate in by(Predicate<? super E>).

Implementation

So far so good, but how is this design going to impact the implementation of our interfaces?

It turns out the implementation is going to be pretty straightforward:

@Immutable
final class PlainItem implements Item {
  private final String name;

    // constructor here (or Lombok's @AllArgsConstructor)

    // name() method here (or Lombok's @Getter @Accessors(fluent = true))
}

@Immutable
final class PlainGroup implements Group {
    // I'm using com.google.common.collect.ImmutableList
    private final ImmutableList<PlainItem> items;

    // constructor here

    // items() method here

    @Override
    public Filterer<? extends PlainGroup, ? extends PlainItem> filtered() {
        return this::filteredGroup; // the best part (instance method reference)
    }

    private PlainGroup filteredGroup(Predicate<? super PlainItem> predicate) {
        return new PlainGroup(filteredItems(predicate));
    }

    private ImmutableList<PlainItem> filteredItems(Predicate<? super PlainItem> predicate) {
        return this.items.stream().filter(predicate).collect(ImmutableList.toImmutableList());
    }
}

As you can see, we have a classic method for providing the filtered version of the PlainGroup (i.e. filteredGroup). However, this method has been made private, and is used only as an instance method reference, thus capturing this object. As a result, we never even have to create a real implementation of the Filterer interface!

As far as I know (correct my if I am wrong), the extra object creation in filtered will not exhibit any performance penalty because JVM's escape analysis will be triggered (as long as the object is consumed right after its creation, of course).

Usage

Just a short (and obvious) code sample showing how this looks when used:

@Test
public void testFiltered() {
    ImmutableList<PlainItem> items = ImmutableList.of(
        new PlainItem("a"),
        new PlainItem("b"),
        new PlainItem("ab")
    );
    PlainGroup group = new PlainGroup(items);

    PlainGroup filteredGroup = group.filtered().by(item -> item.name().startsWith("a"));

    Assert.assertEquals(2, filteredGroup.items().size());
    Assert.assertFalse(filteredGroup.items().contains(items.get(1)));
}

Playing With Filterer

Generic Filterer

For clarity, I defined Filterer above to depend on Group and Item. But note that Filterer can be made completely generic (i.e. without the ? extends in type parameters):

@FunctionalInterface
interface Filterer<G, E> {
    G by(Predicate<? super E> predicate);
}

Such a generic interface can be reused everywhere then, provided it is used with appropriate upper bounds (? extends). In order to apply it to Group, we would write:

interface Group {
    List<? extends Item> items();

    Filterer<? extends Group, ? extends Item> filtered();
}

Filterer with Syntactic Sugar Methods

On the other hand, if we do not make the interface generic, we can introduce some syntactic-sugar default methods to it:

@FunctionalInterface
interface Filterer<G extends Group, E extends Item> {
    G by(Predicate<? super E> predicate);

    default G byName(String name) {
        return by(item -> item.name().equals(name));
    }
}

We can even go as far as creating subtypes of Filterer with specialized default methods:

@FunctionalInterface
interface ScoredFilterer<G extends ScoredGroup, E extends ScoredItem> extends Filterer<G, E> {
    default G byMinScore(int minScore) {
        return by(item -> item.score() >= minScore);
    }
}

interface ScoredGroup extends Group {
    @Override
    List<? extends ScoreItem> items();

    @Override
    ScoredFilterer<?, ?> filtered();
}

As you can see, this pattern is quite flexible.

Summary

I have shown here how one can use a helper interface (dubbed Filterer) to provide objects using it with convenient means of returning filtered versions of themselves.

I found this design pattern useful on a few occasions now, and I hope you might find it useful too.

Thank you for reading.