2. 开发基本的递归线性表处理函数¶
2.1. 递归线性表处理示例：sum( list )¶
在上一节中，我们介绍了 fp 模块中的三个谓词，即 isEq、isZero 和 isNull。现在我们将介绍一些额外的谓词和算术函数，随后将使用它们来编写递归线性表处理函数，包括 sum 、 isMember 、 removeFirst 和 subst 。
首先，要检查某物是否为线性表，必须使用 isList 函数:
> fp.isList( [ ] ) true > fp.isList( [1,2,3] ) true > fp.isList( 1 ) false
其次，两个辅助函数 add 和 sub 分别对其两个整数参数执行加法和减法操作:
> fp.add(2,3) 5 > fp.sub(2,3) -1
第三，两个谓词 isLT 和 isGT 分别测试其第一个参数是否小于或大于第二个参数:
> fp.isGT(2,3) false > fp.isLT(2,3) true
我们现在准备编写一个递归的 sum 函数，该函数接收一个整数线性表，并返回输入线性表中所有值的总和。:
> var fp = require('./fp') > sum( [ 1, 2, 3 ] ) 6 > sum( [ ] ) 0 > sum( [ 1, -2, 3, -4] ) -2
当我们在线性表上设计递归算法时，必须牢记整数线性表的递归 BNF 定义：
遵循此语法中 <list_of_ints> 的两条路径（一条对应空线性表，另一条对应非空线性表），可构建如下所示的 sum 函数。
思考如何完成这个函数。
然后尝试下面的复习题，它使用了类似的递归线性表处理逻辑。注意，此问题是随机生成的。你必须连续三次正确解答才能获得与之相关的分数。
2.2. 递归线性表处理示例：isMember( num, list )¶
接下来考虑一个函数 isMember，它接收一个整数 n 和一个整数线性表 ns，当且仅当其第一个参数是第二个参数的成员时返回真:
> var fp = require('./fp') > isMember( 2, [ 1, 2, 3 ] ) true > isMember( 4, [ 1, 2, 3 ] ) false > isMember( 2, [ 1, [ 2, 3 ] ] ) false
请注意，上述最后一次调用中的第二个参数不是整数线性表。请记住整数线性表的递归定义：
遵循此递归定义，我们使用下方第一张幻灯片提供的模板为 isMember 设计了一个递归算法。
参考 isMember 的递归模式，思考如何设计一个类似的线性表处理函数 removeFirst，该函数接收一个整数 n 和一个整数线性表 l，并返回一个与 l 相同但移除了 n 首次出现的线性表:
> var fp = require('./fp') > removeFirst(3,[1,2,3]) [ 1, 2 ] > removeFirst(4,[1,2,3]) [ 1, 2, 3 ] > removeFirst(2,[1,2,3,2]) [ 1, 3, 2 ]
一旦你为 removeFirst 获得了正确的逻辑，请考虑以下复习问题，该问题要求你对 removeFirst 进行轻微修改。
2.3. 递归线性表处理示例：subst( new, old, list )¶
作为本节的最后一个示例，考虑一个函数，它接收两个整数 \(n\) （代表“新”）和 \(o\) （代表“旧”）以及一个整数列表 \(l\) ，并返回一个与 \(l\) 相同的列表，只不过 \(l\) 中所有出现的 \(o\) 都被替换为 \(n\)
> var fp = require('./fp') > subst(10,1,[1,2,3,2,1]) [ 10, 2, 3, 2, 10 ] > subst(50,5,[1,2,3]) [ 1, 2, 3 ] > subst(10,1,[[1,2],3]) [ [ 1, 2 ], 3 ]
请注意，我们稍微扩展了 subst 函数的语义，因为上述最后一次调用中的第三个参数并非整数列表。同样，subst 函数的模板遵循由 <list_of_ints> 的 BNF 文法所建立的模式。
现在我们已经确立了该函数的正确逻辑，请考虑本节最后的复习题，该题要求你对 subst 函数进行轻微修改。
