1.1. 使用 fp.cons 构建线性表¶

函数式编程 （FP）是一种编程范式，其中函数是主要的抽象概念，且函数为纯函数、一等公民，数据不可变。

如果函数返回值且无任何副作用，则称其为 纯 函数。纯函数不会影响其外部的任何数据（无赋值语句、无 I/O），也不会访问可能被其他函数更改的任何全局数据。给定相同的输入，纯函数总是返回相同的值，就像在数学中一样。事实上，FP 始于 Alonzo Church 的 \(\lambda\) -演算，我们将在本课程稍后部分进行研究。

一等值 （如整数、布尔值、字符串等）是可以赋值给变量、可以存储在数组和其他数据结构中、可以作为函数调用的参数以及可以作为函数调用返回值的值。在 FP 中，函数是一等值。将一个或多个函数作为参数和/或返回一个函数的函数称为 高阶函数 （稍后会详细介绍）。

在函数式编程中，所有数据项都是 不可变的：一旦创建了某个值，就永远无法修改它。即使在 Java 这种面向对象而非函数式编程语言中，String 对象也是不可变的。

FP 语言中最基本、内置的数据结构是线性表，其结构可用 BNF 记法描述如下：

请注意：

1. 我们目前将范围限定为整数线性表，且

2. 上述文法描述了线性表的 抽象语法或结构，而非其 具体语法，即列表在任何特定函数式编程语言中的实际表现形式。

在本函数式编程章节中，线性表的具体语法将使用方括号包围每个线性表，并在表中每对连续元素之间使用逗号分隔。

因此，空线性表将表示为:

[ ]

非空线性表将如下所示:

[2, 3, 5, 7, 11, 13, 17, 19]

由于 JavaScript（JS）没有内置的不可变线性表数据结构，我们将其作为名为 fp.js 的模块的一部分提供，该模块在本章中广泛使用。

只要该模块位于当前目录中，您就可以在 JS 文件顶部包含以下行，使其在文件中可用：

var fp = require('./fp');

然后，每次你想使用该模块中定义的任何函数（例如即将描述的 hd 函数）时，都需要在函数名前加上前缀 fp. 。例如，你可以这样调用带有参数 list 的 hd 函数:

fp.hd(线性表)

线性表可以使用 cons 函数构建，该函数接受两个参数：单个元素和元素线性表。 cons 函数返回一个新线性表，其内容与第二个参数相同，但在前面插入了第一个参数。因此，在 node:: 提供的读取 - 求值 - 打印循环中：

> fp.cons( 5, [1,2,3] ) [ 5, 1, 2, 3 ] > fp.cons( 1, [ ] ) [ 1 ]

fp 模块提供了一个辅助函数，用于在一次调用中创建任意长度的线性表，如下所示：

> fp.makeList(1,2,3)
[ 1, 2, 3 ]
> fp.makeList(1,2,3,4,5,6,7,8,9,10)
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
> fp.makeList()
[]

下列问题涉及 fp.cons 函数的语法与语义。

1.2. 使用 fp.hd 和 fp.tl 解构线性表¶

目前，我们可以使用 fp.cons 和 fp.makeList 构造器来构建线性表。然而，我们还需要能够访问线性表中的元素。

fp 模块提供了所谓的“头”和“尾”访问器。

• fp.hd(l) 返回其线性表参数的第一个元素。

• fp.tl(l) 返回通过从其线性表参数中移除头元素而得到的线性表。

> fp.hd([1,2,3])
1
> fp.tl([1,2,3])                  // how would you access the second or third element of this list?
[ 2, 3 ]
> fp.hd([])
Error: hd can only be called with a non-empty list.
> fp.tl([])
Error: tl can only be called with a non-empty list.

在 Lisp 和 Scheme 等语言中，这些访问器分别称为"car"和"cdr"。

需要注意的是 cons 构造函数与线性表访问器之间的对称性： cons 使用访问器返回的相同构建块来构建线性表。

以下练习题涉及 fp.hd 、 fp.tl 和 fp.cons 函数的语义。请注意，此问题是随机生成的。您必须连续三次正确解答才能获得与之相关的分数。

1.3. 使用 fp 模块练习线性表操作¶

本题帮助你复习 fp.hd 、 fp.tl 和 fp.cons 函数的语义。

1.4. fp.isNull、fp.isEq 和 fp.isZero¶

要检查线性表是否为空，必须使用 'isNull ' 函数：

> fp.isNull( [ ] )      // we say that a list is null when it is equal to [ ]
true
> fp.isNull( [1,2,3] )
false

isNull 函数是一个 谓词，即返回布尔值 true 或 false 的函数。

第二个有用的谓词是'isEq '，它用于检查两个 基本元素 是否相等（注意整数是基本元素，但线性表不是）：

> fp.isEq(1,1)
true
> fp.isEq(1,2)
false

第三个有用的谓词是'isZero '：

> fp.isZero(0)
true
> fp.isZero(1)
false

本节最后一个问题涉及 fp.hd 、 fp.tl 和 fp.isEq 函数的语法与语义。