OpenDSA 完整目录

Chapter 28 Functional Programming

| 关于   «  6. 过程式抽象:Map、Curry 和 Compose   ::   目录   ::   8. 组合 Map 与 Reduce  »

7. 过程抽象:过滤模式与折叠(或归约)模式

7.1. 过滤模式

下面举例说明了过滤(或简称为 filter)模式。在右侧的例子中,使用 JavaScript 的取模运算符 % 来测试一个整数是否为偶数。

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

注意,利用 curry ,我们可以使用 filter 函数来实际创建 keepPositive 和 keepEven 这两个函数。

> var keepPositive = fp.curry(filter)(function (n) { return fp.isGT(n,0); });
> var keepEven = fp.curry(filter)(function (n) { return fp.isZero(n % 2); });

这说明了柯里化创建函数的能力。它使我们不仅能够复制 keepPositive 和 keepEven 这类单个函数的行为,还能复制这些函数本身,而完全不必编写它们的代码。

下面第一道题涉及过滤模式。

7.2. 折叠/归约模式

为了发现我们的下一个模式,回忆一下,在 使用辅助函数编写 reverse 和 split 函数 一节中,我们使用了一个带累加器的辅助函数,在发起递归调用之前(而不是从递归调用返回之后)执行 cons 操作。在寻找下面两个例子的共同点时,请记住这一点。

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

我们在前面例子中定义的 reduce 函数,在遍历列表时按从左到右的顺序应用其辅助函数 f 来产生累加值 acc 。此外,它是以所谓的 尾递归 方式做到这一点的,因为辅助函数 f 是在递归调用的实参中应用的,而不是应用在递归调用所返回的结果上。这种从左到右的顺序对于 reverse 的定义能够正确工作至关重要。对于 sum 来说则无关紧要,因为加法满足交换律。我们将在 section on continuation passing style 中更详细地讨论尾递归函数。

我们也可以定义一个类似的函数,它在遍历列表时按从右到左的顺序应用辅助函数。下一组例子对此进行了说明。

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

注意, reduceRight 函数期望我们传入用于“累加”值的那个操作函数,其第一个参数表示列表的表头,也就是“下一个”要被累加的值。它的第二个参数因此就是累加器。这与 reduce 相反,后者期望的函数中第一个参数扮演累加器的角色,第二个参数则是“下一个要被累加的值”。这强调了这两种模式在右结合性与左结合性上的区别。

还要注意,由于 reduce 按照我们在 the section on helper functions 中描述的方式捕获了累加模式,当到达列表末尾时,累加器已经完成了为得到最终答案所需的全部计算。 reduceRight 则不是这样,因为它把函数参数 f 应用于发起递归调用的结果,而不是把递归应用于应用 f 的结果。 reduce 所接受的 acc 参数是一个真正的累加器,它在深入递归的过程中逐步累积自己的值,因此到达基本情况时全部必要的计算都已完成。 reduceRight 所接受的 acc 参数仅仅是一个起点,值的累积必须在我们从到达基本情况处递归上升的过程中完成。

下面这道题涉及上面描述的归约模式。

7.3. 映射模式与归约模式练习

下面这道题同时使用映射模式和归约模式。

7.4. 归约模式更多练习

下面这道题将让你密集练习归约模式。这道题是随机化的,必须连续三次答对。

   «  6. 过程式抽象:Map、Curry 和 Compose   ::   目录   ::   8. 组合 Map 与 Reduce  »

关闭窗口