纯函数式并行编程：组合子的泛化与设计原则

### 纯函数式并行编程：组合子的泛化与设计原则 #### 1. 选择 API 法则的方法 在设计 API 时，为其选择合适的法则至关重要。以下是几种可考虑的方法： - **基于概念模型推理**：思考概念模型，从中推导出应该成立的法则。 - **发明有用法则**：创造你认为可能有用或有指导意义的法则，然后验证它们是否能在你的模型中成立。 - **依据实现推导**：查看实现，根据其来提出你期望成立的法则。不过这种方法相对较弱，因为法则可能只是反映了实现，即使实现有缺陷或需要特殊的副作用条件，也会使组合变得困难。 #### 2. 组合子的泛化过程 ##### 2.1 从 `choice` 到 `choiceN` 假设我们需要一个函数，根据初始计算的结果在两个并行计算中进行选择： ```scala def choice[A](cond: Par[Boolean])(t: Par[A], f: Par[A]): Par[A] ``` 其简单的阻塞实现如下： ```scala def choice[A](cond: Par[Boolean])(t: Par[A], f: Par[A]): Par[A] = es => if cond.run(es).get then t(es) else f(es) ``` 但这里使用 `Boolean` 且只在两个并行计算中选择有些局限。更通用的做法是能在 N 个计算中选择： ```scala def choiceN[A](n: Par[Int])(choices: List[Par[A]]): Par[A] ``` `choiceN` 运行 `n`，然后用其结果从 `choices` 中选择一个并行计算，它比 `choice` 更通用。 **练习 7.11**：实现 `choiceN` 并使用 `choiceN` 实现 `choice`。 ```scala def choiceN[A](n: Par[Int])(choices: List[Par[A]]): Par[A] = es => val index = n.run(es).get % choices.size choices(index).run(es) def choice[A](cond: Par[Boolean])(t: Par[A], f: Par[A]): Par[A] = choiceN(cond.map(b => if b then 0 else 1))(List(t, f)) ``` ##### 2.2 从 `choiceN` 到 `choiceMap` `choiceN` 中使用 `List` 作为容器也显得过于具体。如果使用 `Map` 来存储计算结果会怎样呢？ ```scala def choiceMap[K, V](key: Par[K])(choices: Map[K, Par[V]]): Par[V] ``` `choiceMap` 的实现与 `choiceN` 类似，只是使用键在 `Map` 中查找： ```scala def choiceMap[K, V](key: Par[K])(choices: Map[K, Par[V]]): Par[V] = es => val k = key.run(es).get choices(k).run ``` ##### 2.3 统一为 `chooser` 观察 `choice`、`choiceN` 和 `choiceMap`，发现它们本质上都是使用一个函数来进行选择。因此，可以将它们统一为更通用的 `chooser`： ```scala extension [A](pa: Par[A]) def chooser[B](choices: A => Par[B]): Par[B] ``` 实现如下： ```scala extension [A](pa: Par[A]) def chooser[B](choices: A => Par[B]): Par[B] = es => val a = pa.run(es).get choices(a).run ``` 使用 `chooser` 实现 `choice` 和 `choiceN`： ```scala def choice[A](cond: Par[Boolean])(t: Par[A], f: Par[A]): Par[A] = cond.chooser(b => if b then t else f) def choiceN[A](n: Par[Int])(choices: List[Par[A]]): Par[A] = n.chooser(i => choices(i % choices.size)) ``` ##### 2.4 引入 `flatMap` 和 `join` `chooser` 通常也被称为 `flatMap`