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

参考链接：

1. 定义与概念

Primitives，即原语，是系统或语言中最基础、不可再分的构建块（building blocks）。原语是直接由底层实现提供的原子操作或数据类型，无法通过其他更简单的元素组合而成。在编程语言中，原语是编译器直接支持的数据类型或操作，比如整数 int、字符 char、布尔 boolean，以及基本的算术操作、比较操作等。

Combinator，即组合子，特指在计算中不引用任何自由变量的函数。它本身不直接实现功能，而是通过组合已有的组件来构建更复杂的行为。所有的变量都是作为参数传递给它的，组合子是不依赖外部环境的纯函数。组合子的概念最早由美国数学家 Haskell Brooks Curry 在 20 世纪 20 年代提出，用于研究函数和变量的基本性质。

Combinator Pattern 中使用的原语是域（domain）中最简单的元素，比如整数域中的加法和乘法。Combinator Pattern 提供了将原语和已经组合成的结构组合成更复杂结构的手段，比如组合乘法和加法。

原语是「基础」，组合子是「胶水」：

  • 原语提供原子能力，是构建一起的起点。
  • 组合子通过组合这些原语（或更低阶的组合子）实现复杂的逻辑。

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

2. 校验用户信息

2.1 使用组合子校验

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 表示用户信息是有效的，以函数式编程的方式来编码，可以得到以下代码：

1
2
3
4
5
6
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 类中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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。

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

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

2.2 完善校验结果

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public interface ValidationResult {
    /**
     * 是否合法
     */
    boolean isValid();

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

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

    /**
     * 获取一个非法的校验结果
     */
    static ValidationResult invalid(String reason) {
        return new Invalid(reason);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 必须要调整：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
        };
    }
}
1
2
3
4
5
6
7
8
9
@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 中的任意一个
  • …

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

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

3.2 代码实现

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

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

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

1
2
3
4
5
6
7
8
9
10
11
/**
 * <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：同时包含
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 先用当前 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()，为了不影响整体的阅读体验，有一个它的使用细节放在了文末的补充内容中。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * @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<>();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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. FizzBuzz

FizzBuzz 是一款儿童游戏，它要求一群孩子围成一个圈，按顺序报数：

  • 如果一个数字是 3 的倍数，对应位置的孩子要说“Fizz”而不是数字；

  • 如果一个数字是 5 的倍数，对应位置的孩子要说“Buzz”而不是数字；

  • 如果一个数字同时是 3 和 5 的倍数，对应位置的孩子要说“FizzBuzz”而不是数字；

  • 如果说错了，那他就会被淘汰出局，游戏继续，直到只剩下最后一个人。

这也是一种常见的编程面试题，要求候选人按照以上规则打印从 1 到 n 的所有数字。

逻辑并不难，要实现也很简单，但如果是用 Combinator Pattern 来实现呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class FizzBuzz {

    public static Function<Integer, String> fizzBuzz() {
        return FizzBuzzFunction.fizzbuzz()
                .orElse(FizzBuzzFunction.fizz())
                .orElse(FizzBuzzFunction.buzz())
                .orElse(FizzBuzzFunction.number());
    }

    private interface FizzBuzzFunction extends Function<Integer, String> {
        static FizzBuzzFunction word(String word) {
            return i -> word;
        }

        default FizzBuzzFunction ifDivisibleBy(int modulo) {
            return i -> i % modulo == 0 ? apply(i) : "";
        }

        static FizzBuzzFunction fizz() {
            return word("fizz").ifDivisibleBy(3);
        }

        static FizzBuzzFunction buzz() {
            return word("buzz").ifDivisibleBy(5);
        }

        static FizzBuzzFunction fizzbuzz() {
            return fizz().and(buzz());
        }

        static FizzBuzzFunction number() {
            return String::valueOf;
        }

        default FizzBuzzFunction and(FizzBuzzFunction other) {
            return i -> {
                String first = this.apply(i);
                String second = other.apply(i);
                return (first.isEmpty() && second.isEmpty()) ? "" : first + second;
            };
        }

        default FizzBuzzFunction orElse(FizzBuzzFunction other) {
            return i -> {
                String first = this.apply(i);
                if (first.isEmpty()) {
                    return other.apply(i);
                }
                return first;
            };
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
@Test
public void testFizzBuzz() {
    String str = FizzBuzz.fizzBuzz().apply(3);
    assertThat(str).isEqualTo("fizz");

    str = FizzBuzz.fizzBuzz().apply(5);
    assertThat(str).isEqualTo("buzz");

    str = FizzBuzz.fizzBuzz().apply(15);
    assertThat(str).isEqualTo("fizzbuzz");
}

FizzBuzzFunction 中的部分方法可能有点难以理解，比如 word()、ifDivisibleBy() 以及它们俩组成的 fizz()、buzz() 等方法。

首先得明白：

  • word() 是一个静态方法（又或者说是静态工厂），它返回一个 FizzBuzzFunction 实例，针对这个实例，如果调用它的 apply() 方法，按照 word() 方法的实现，就会返回传入的 word 字符串；
  • ifDivisibleBy() 是一个由 default 关键字修饰的方法，相当于是成员方法，只能通过 FizzBuzzFunction 实例进行调用。

以 fizz() 为例：

1
2
3
static FizzBuzzFunction fizz() {
    return word("fizz").ifDivisibleBy(3);
}

它首先调用了 word("fizz")，这相当于创建了一个 FizzBuzzFunction 实例，如果调用这个实例的 apply() 方法，无论传入什么，都会返回 fizz 字符串，因为 word() 方法的实现就是这个意思：

1
2
3
static FizzBuzzFunction word(String word) {
    return i -> word;
}

然后在创建的 FizzBuzzFunction 实例的基础上调用了 ifDivisibleBy(3)，它的实现是：

1
2
3
default FizzBuzzFunction ifDivisibleBy(int modulo) {
    return i -> i % modulo == 0 ? apply(i) : "";
}

也就是说，如果一个数能被传入的 modulo 整除，就调用 apply(i) 作为返回值，否则返回空字符串。

ifDivisibleBy(3) 就相当于如果一个数能被 3 整除，就调用 apply(i) 作为返回值。

还记得前面说的吗？

通过 word() 方法创建出的 FizzBuzzFunction 实例，调用其 apply() 方法时，将返回传入的字符串。

因此 fizz() 方法表示的含义是：如果一个数能被 3 整除，就返回 fizz 字符串，否则返回空字符串。

其余的方法也能按照类似的思路来理解，就不赘述了。

5. 实现总结

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

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

实现的关键是对原语和组合子的定义，如何定义出能够复用的原语、如何定义出能够将原语进行组合的组合子，两者息息相关，要互相考虑，这之间没有固定的公式模板，只有多写、多练、多思考才能融会贯通。

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

flatMap() 的并不难，日常开发也经常使用，那下述代码的执行流程又是怎么样的呢？

说实话，我第一次看到的时候也懵了一会。

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

flatMap-2