封面来源：碧蓝航线愚者的天平活动 CG

参考链接：

1. 定义与概念

Combinator，即组合子，它是计算机科学中的一个概念，特指在计算中不引用任何自由变量的函数。该概念最早由美国数学家 Haskell Brooks Curry 在 20 世纪 20 年代提出，用于研究函数和变量的基本性质。组合子主要应用在函数式编程中，用于构建和操作复杂的函数和数据结构。

Primitives，即基元，它和组合子都是抽象的名称。在编程语言中，基元类型是编程语言中编译器直接支持的数据类型，比如整数 int，字符 char，布尔值 boolean 等。Combinator Pattern 中使用的基元是域（domain）中最简单的元素，比如整数域中的加法和乘法。Combinator Pattern 提供了将基元和已经组合成的结构组合成更复杂结构的手段，比如组合乘法和加法。

在 Java 中，组合子的概念并不常见，因为 Java 是一门面向对象的编程语言，而组合子更多的是在函数式编程语言中使用。Java 8 中引入了 Lambda 表达式和函数式接口，在 Java 中也能使用一些函数式编程的概念，包括组合子。

2. 校验用户信息

2.1 使用组合子校验

假设现在需要校验用户信息，当用户的 name 不为空，并且 email 中包含 @ 符号，那这个用户信息就是合法的。最直接的做法是在 User 类中添加校验的方法：

public record User(String name, int age, String email) {

    public boolean isValid() {
        return nameIsNotEmpty() && eMailContainsAtSign();
    }

    private boolean nameIsNotEmpty() {
        return !name.trim().isEmpty();
    }

    private boolean eMailContainsAtSign() {
        return email.contains("@");
    }
}

1	new User("mofan", 22, "cy.mofan@foxmail.com").isValid(); // true

这看起来很不错，但也有一些缺点。当校验规则发生变化时应该怎么办？

比如在某些案例中，要求用户的年龄要大于 16。在这种情况下，首先能想到的解决方式是修改 isValid() 方法，但这似乎违背了 SRP（单一职责原则，Single Responsibility Principle）。

在重构并把校验逻辑提取到新类之前，需要静下心来好好想想到底要表达什么。

当且仅当给定的一组校验规则得到满足时，用户信息才是有效的。每个校验规则描述了用户必须具备的属性。不同的规则可以组合成更复杂的规则。

执行一组校验规则时会产生一个校验结果，假设用布尔值 true 表示用户信息是有效的，以函数式编程的方式来编码，可以得到以下代码：

public interface UserValidation extends Function<User, Boolean> {}
UserValidation nameIsNotEmpty = user -> !user.name.trim().isEmpty();
UserValidation eMailContainsAtSign = user -> user.email.contains("@");
User mofan = new User("mofan", 22, "cy.mofan@foxmail.com");

nameIsNotEmpty.apply(mofan) && eMailContainsAtSing.apply(mofan); // true

这里有些样板代码：

为什么要自己创建 nameIsNotEmpty 和 eMailContainsAtSign 规则？
为什么要使用 && 手动合并结果？
为什么有 1 行应用代码却有 4 行初始化代码？

尽管这段代码有些冗长，但它已经包含了构建 Combinator Pattern 的所有要素： nameIsNotEmpty 和 eMailContainsAtSign 是基元，&& 是组合子。使用 Java 8 可以将这些要素移动到 UserValidation 类中：

interface UserValidation extends Function<User, Boolean> {
    static UserValidation nameIsNotEmpty() {
        return user -> !user.name.trim().isEmpty();
    }

    static UserValidation eMailContainsAtSign() {
        return user -> user.email.contains("@");
    }

    default UserValidation and(UserValidation other) {
        return user -> this.apply(user) && other.apply(user);
    }
}

User mofan = new User("mofan", 22, "cy.mofan@foxmail.com");           nameIsNotEmpty().and(eMailContainsAtSign()).apply(mofan); // true

在上述代码中，基元被转换为静态方法，组合子被转换为 default 方法。nameIsNotEmpty 和 eMailContainsAtSign 两个基元都返回了以 UserValidation 为目标类型的 Lambda 表达式，与基元不同的是，组合子使用 && 操作符来组合 UserValidation。

采用上述这种方式来验证用户信息有两个优点：

基元在组合时没用立即被应用，这意味着需要先构建 UserValidation 然后再执行它。使用这种方式，能够将 UserValidation 作用于更多需要被校验的用户；
UserValidation 是 无状态的，它能够在并行环境下执行，而不会出现竞争。

2.2 完善校验结果

将 Boolean 类型作为校验结果是合理的吗？

一般来说，内置语言类型通常不适合用来表示域（domain）信息。原因有两点：

在 Java 中，很难修改不属于自己的代码。这就像不能在 Boolean 类型中添加一个 query() 方法，这使得很难确定究竟是哪些规则让用户信息校验不过。简单来说，一个 Boolean 类型没法表示出更多的细节信息，比如用户信息校验失败时，究竟是哪些规则导致的失败呢。
内置类型的语义是隐式的、特定与上下文的。例如在校验用户信息的上下文中，true 表示用户信息是有效的。如果把这个校验结果传递给其他上下文时，这个假设就可能会不成立。

针对当前场景而言，需要一个新的校验结果类型 ValidationResult，它包含了在特定规则下，用户信息无效的原因。

public interface ValidationResult {
    /**
     * 是否合法
     */
    boolean isValid();

    /**
     * 非法信息
     */
    Optional<String> getReason();

    /**
     * 获取一个合法的校验结果
     */
    static ValidationResult valid() {
        return ValidationSupport.valid();
    }

    /**
     * 获取一个非法的校验结果
     */
    static ValidationResult invalid(String reason) {
        return new Invalid(reason);
    }
}

class Invalid implements ValidationResult {

    private final String reason;

    public Invalid(String reason) {
        this.reason = reason;
    }

    @Override
    public boolean isValid() {
        return false;
    }

    @Override
    public Optional<String> getReason() {
        return Optional.of(this.reason);
    }
}

final class ValidationSupport {
    private static final ValidationResult valid = new ValidationResult() {
        @Override
        public boolean isValid() {
            return true;
        }

        @Override
        public Optional<String> getReason() {
            return Optional.empty();
        }
    };

    public static ValidationResult valid() {
        return valid;
    }
}

校验结果要么是有效，要么是无效。ValidationResult 实例的相等性体现在类型和属性上。如果要两个 Invalid 相等，那么它们的 reason 属性值也要相等。

针对校验成功的场景，使用 ValidationSupport.valid() 方法返回 ValidationResult 单例。

为了使用 ValidationResult，先前的 UserValidation 必须要调整：

public interface UserValidation extends Function<User, ValidationResult> {
    static UserValidation nameIsNotEmpty() {
        return holds(user -> !StringUtils.trim(user.name()).isEmpty(), "Name is empty.");
    }

    static UserValidation eMailContainsAtSign() {
        return holds(user -> StringUtils.contains(user.email(), "@"), "Missing @-sign.");
    }

    private static UserValidation holds(Predicate<User> predicate, String reason) {
        return user -> predicate.test(user)
                ? ValidationResult.valid()
                : ValidationResult.invalid(reason);
    }

    default UserValidation and(UserValidation other) {
        return user -> {
            ValidationResult res = this.apply(user);
            return res.isValid() ? other.apply(user) : res;
        };
    }
}

@Test
public void testValidateUser() {
    UserValidation validation = UserValidation.nameIsNotEmpty().and(UserValidation.eMailContainsAtSign());

    User emptyNameUser = new User("", 22, "mail@xx.com");
    ValidationResult result = validation.apply(emptyNameUser);
    assertThat(result.isValid()).isFalse();
    assertThat(result.getReason()).isPresent().hasValue("Name is empty.");
}

基元 holds() 接收给定的 Predicate 参数值，返回单例 valid 或新实例 Invalid。基元 nameIsNotEmpty() 和 eMailContainsAtSign() 通过重构后不再返回布尔值，而是 UserValidation 实例。

组合子 and() 只在当前校验结果是单例 valid 时，才会计算传入的 other 对象。以测试方法 testValidateUser() 为例，如果 nameIsNotEmpty() 返回的是 Invalid 实例，将不会执行 eMailContainsAtSign()。从开发人员的角度来看，与返回布尔值相比，返回 UserValidation 能够传递更多的信息。

这种设计也有一些缺陷，在某些情况下可能需要包含所有规则的校验结果，但由于组合子 and() 是短路的，无法实现这样的功能，此时需要一个组合子 all() 来执行所有校验规则，它的签名会是这样的：

1
2
3

static UserValidation all(UserValidation... validations) {
    // --snip--
}

3. 查找目标行

3.1 需求分析

给定一个多行文本 text（以换行符 \n 分割的普通字符串），然后获取多行文本中符合某些规则的行（最终返回 List<String>）。

对于一行文本，应用在其上的规则通常只有两种：

包含某些字符串
不包含某些字符串

但根据这两种规则能够派生出许多复杂的规则，比如：

包含字符串 A 或字符串 B，但不包含字符串 C
包含字符串 A，但不包含字符串 B、C 中的任意一个
包含所有字符串 A、B、C
包含字符串 A、B、C 中的任意一个
…

从当前描述来看，包含与 不包含 是两个基元，将他们组合后能够得到许多组合子。

再深度思考下，不包含 其实是包含的取反操作，不包含 其实就是在目标行中移除包含的行。比如现有 $\Alpha$ 、 $\Beta$ 、 $\Gamma$ 三行字符串，需要获取不包含字符串 $\alpha$ 的字符串，已知字符串 $\alpha$ 存在于 $\Alpha$ 中，此时将 $\Alpha$ 从三行字符串中移除即可得到不包含字符串 $\alpha$ 的 $\Beta$ 和 $\Gamma$ 两行字符串。按照这样的理解，不包含 其实也是一种组合子，包含是唯一的基元。

3.2 代码实现

声明 Finder 接口，定义 find() 方法，用于在多行文本 text 中查找出目标行：

public interface Finder {
    /**
     * 在文本中找到每行
     */
    List<String> find(String text);
}

在 Finder 内部定义静态方法 contains()，相当于是 Finder 的默认实现：

/**
 * <p>相当于接口的默认实现。</p>
 * <p>
 * 在实现中将传入字符串 txt 按换行符拆分，返回包含指定 word（忽略大小写）的所有行。
 * </p>
 */
static Finder contains(String word) {
    return txt -> Stream.of(txt.split("\n"))
            .filter(i -> i.toLowerCase().contains(word.toLowerCase()))
            .collect(Collectors.toList());
}

contains() 也相当于是一个基元，就像前文 UserValidation 中的 nameIsNotEmpty() 和 eMailContainsAtSign() 一样。

基于 contains() 基元，能够派生出一系列组合子，比如：

not：不包含
or：包含任意一个
and：同时包含

/**
 * 先用当前 finder 查找出所需要的行，然后再移除使用
 * notFinder 查找出的所有行。
 */
default Finder not(Finder notFinder) {
    return txt -> {
        List<String> res = this.find(txt);
        res.removeAll(notFinder.find(txt));
        return res;
    };
}

/**
 * 先用当前 finder 查找出所需要的行，然后再追加使用
 * orFinder 查找出的所有行。
 */
default Finder or(Finder orFinder) {
    return txt -> {
        List<String> res = this.find(txt);
        res.addAll(orFinder.find(txt));
        return res;
    };
}

/**
 * 先用当前的 finder 查找出所需要的行，再以这些行作为原始
 * 文本，使用 andFinder 再查找出满足要求的行，最后把这些
 * 行扁平化处理得到最终的结果。
 */
default Finder and(Finder andFinder) {
    return txt -> this.find(txt).stream()
            .flatMap(i -> andFinder.find(i).stream())
            .collect(Collectors.toList());
}

和 UserValidation 一样，组合子都是由 default 修饰的默认方法。

或许这些组合子比较难以理解，但细想一下其实不难，把它们当成匿名内部类就行。not 和 or 的实现很类似，and 的实现则是使用了 Stream#flatMap()，为了不影响整体的阅读体验，有一个它的使用细节放在了文末的补充内容中。

为了方便使用，这些组合子还能够进一步组合，以工具类的方式将不同的查找规则展现出来：

/**
 * @author mofan
 * @date 2024/3/17 22:49
 */
public class Finders {
    private Finders() {
    }

    /**
     * 包含 query 或 orQuery 的，但不包含 notQuery 的行
     */
    public static Finder advancedFinder(String query, String orQuery, String notQuery) {
        return Finder.contains(query)
                .or(Finder.contains(orQuery))
                .not(Finder.contains(notQuery));
    }

    /**
     * 包含 query 的，但不包含任一 excludeQuires 的行
     */
    public static Finder filteredFinder(String query, String... excludeQueries) {
        var finder = Finder.contains(query);
        for (String excludeQuery : excludeQueries) {
            finder = finder.not(Finder.contains(excludeQuery));
        }
        return finder;
    }

    /**
     * 包含所有 queries 的行
     */
    public static Finder specializedFinder(String... queries) {
        Finder finder = identMulti();
        for (String query : queries) {
            finder = finder.and(Finder.contains(query));
        }
        return finder;
    }

    /**
     * 包含任一 queries 的行
     */
    public static Finder expandedFinder(String... queries) {
        Finder finder = identSum();
        for (String query : queries) {
            finder = finder.or(Finder.contains(query));
        }
        return finder;
    }

    private static Finder identMulti() {
        return txt -> Stream.of(txt.split("\n")).collect(Collectors.toList());
    }

    private static Finder identSum() {
        return txt -> new ArrayList<>();
    }
}

public class CombinatorTest implements WithAssertions {

    static final String TEXT = """
            It was many and many a year ago,
            In a kingdom by the sea,
            That a maiden there lived whom you may know
            By the name of ANNABEL LEE;
            And this maiden she lived with no other thought
            Than to love and be loved by me.
            I was a child and she was a child,
            In this kingdom by the sea;
            But we loved with a love that was more than love-
            I and my Annabel Lee;
            With a love that the winged seraphs of heaven
            Coveted her and me.""";

    @Test
    public void testFinder() {
        String[] queriesOr = {"many", "Annabel"};
        Finder finder = Finders.expandedFinder(queriesOr);
        List<String> res = finder.find(TEXT);
        assertThat(res).containsExactly(
                "It was many and many a year ago,",
                "By the name of ANNABEL LEE;",
                "I and my Annabel Lee;"
        );

        String[] queriesAnd = {"Annabel", "my"};
        finder = Finders.specializedFinder(queriesAnd);
        res = finder.find(TEXT);
        assertThat(res).singleElement().isEqualTo("I and my Annabel Lee;");

        finder = Finders.advancedFinder("it was", "kingdom", "sea");
        res = finder.find(TEXT);
        assertThat(res).singleElement().isEqualTo("It was many and many a year ago,");

        finder = Finders.filteredFinder(" was ", "many", "child");
        res = finder.find(TEXT);
        assertThat(res).singleElement().isEqualTo("But we loved with a love that was more than love-");
    }
}

4. 实现总结

初次接触 Combinator Pattern 时，可能有些难以理解，但通过上述两个案例的讲解，对于 Combinator Pattern 的实现基本可以总结出一套流程：

定义一个函数式接口（这个函数式接口继承 java.util.function.Function，也可以不继承），内部的 抽象方法接收操作对象类型，返回所需的目标类型。比如校验人员信息时，接收 User 对象，返回校验结果 UserValidation；再比如查找目标行时，接收以 \n 作为分隔符的多行文本 text（实际类型是 String），返回符合要求的 List<String> 类型文本行；
接口中声明 静态方法作为基元，声明 default 方法作为组合子，组合子围绕基元进行组合；
为了便于使用，还可以声明一个工具类，在工具类中使用组合子进一步组合，编写出易用的工具方法。

5. 补充内容

5.1 flatMap

flatMap 是流的扁平化，比如：

1
2
3

List.of(List.of("A", "B", "C"), List.of("D", "E", "F")).stream()
        .flatMap(Collection::stream)
        .collect(Collectors.toList());

它的执行流程是这样的：

flatMap-1

那下述代码的执行流程又是怎么样的呢？

1
2
3

Stream.of("A", "B", "C")
        .flatMap(i -> Stream.of("X", "Y"))
        .collect(Collectors.toList());

flatMap-2