虽然之前对折叠操作进行过一些了解，但是仍然对其不甚熟悉，没法立刻写出定义，最近突然发现一种能方便理解折叠操作的方法，这里对其进行一些记录，使用 js 来进行描述。
该方法似乎无法用来说明为何foldr能处理无穷列表。
啥子是折叠？
对集合的操作，最常用的也就那三种——map，filter，reduce/fold（后面全部使用fold）。其中，map对集合的每一个元素进行相同的映射，返回一个映射后的新集合；filter对集合中的每一个元素进行判断，筛选出符合条件的元素组成返回的集合；而fold操作迭代一个集合，并将每个元素“积累”到同一个值中。
fold操作就是所谓的折叠操作。折叠操作是最原子的——map，filter，flatMap/bind操作都可以由它来实现；折叠操作也可以用于实现某些高层次的业务相关的操作，如 count，groupBy 等。
所以，究竟什么是折叠？根据折叠操作的描述，我们可以认为那些签名为[a] => b的函数都是折叠操作，比如我们有个sum函数，它能够计算一个集合内所有元素的和，这就是一个折叠操作，它的函数签名为[number] => number。
我们规定sum(null) === 0, sum([]) === 0，容易得到sum函数的递归实现——
|
function sum(lst) {
if (lst == null || lst.length === 0) return 0
const [x, ...xs] = lst
return x + sum(xs)
}
|
再考虑一个product函数，它计算一个集合内所有元素的积，我们规定product(null) === 1, product([]) === 1，容易得到它的递归实现——
|
function product(lst) {
if (lst == null || lst.length === 0) return 1
const [x, ...xs] = lst
return x * product(xs)
}
|
可以发现，这两个函数的形式基本一致，我们可以再抽象一层，整出一个所谓的foldr函数。在这里，参数fn就是上面的sum函数的+，product函数的*，我们乘其为折叠函数，init 就是初始值，对sum来说是 0，对product来说是 1。foldr是递归的折叠操作。
|
function foldr(fn, init, lst) {
if (lst == null || lst.length === 0) return init
const [x, ...xs] = lst
return fn(x, foldr(fn, init, xs))
}
|
foldr 使用 Haskell 的中缀函数的形式会容易看许多——
| myFoldr :: (a -> b -> b) -> b -> [a] -> b
myFoldr _ init [] = init
myFoldr fn init (x : xs) = x `fn` myFoldr fn init xs
|
但我们也知道，这些函数也是能够写成尾递归的形式的，这些形式能够抽象成折叠操作吗？答案是 yes，这样尾递归形式（或者就 SICP 的语境上来说，迭代）的折叠操作，我们称为foldl。
| function sum(zero, lst) {
if (lst == null || lst.length == 0) return zero
const [x, ...xs] = lst
return sum(zero + x, xs)
}
function product(zero, lst) {
if (lst == null || lst.zero == 0) return zero
const [x, ...xs] = lst
return product(zero + x, xs)
}
function foldl(fn, zero, lst) {
if (lst == null || lst.length == 0) return zero
const [x, ...xs] = lst
return foldl(fn, fn(zero, x), xs)
}
|
显然，在一般的语言中，foldl 的性能会好于 foldr，因为前者是尾递归形式，能够被优化成循环。
定义姑且是提出来了，但foldl和foldr的区别和对其的感性认识呢？Keep going。
形象表述
一切折叠操作，都可以表示为数组中各元素连同初始值使用特定二元操作符两两连接的形式，而左折叠和右折叠会决定初始值的位置以及该二元操作符的结合性——对于左折叠来说，初始值在最左，该操作符左结合；对于右折叠来说，初始值在最右，该操作符右结合。下面展示一个示例。
考虑一个左折叠操作，假设初始值为 100；折叠函数为>=>，我们可以叫它 fish，简称 f，1 >=> 2等价于f(1, 2)；要折叠的数组为[1, 2, 3]，我们可以这样描述这个折叠操作——
| 100 >=> 1 >=> 2 >=> 3
=> ((100 >=> 1) >=> 2) >=> 3 # 左折叠，左结合
=> f(f(f(100, 1), 2), 3) # 转换成函数调用的形式
=> foldl(f, 100, [1,2,3])
|
右折叠也是如此——
| 1 >=> 2 >=> 3 >=> 100
=> 1 >=> (2 >=> (3 >=> 100))
=> f(1, f(2, f(3, 100)))
=> foldr(f, 100, [1,2,3])
|
右折叠可以使用类似<=<的符号来描述，能很形象地表示运算顺序。
这种形式如何进行推导呢？我们先将其转换为使用>=>（其他符号也行）进行连接的形式，根据结合性按顺序进行函数应用。举个小小的例子——考虑定义一个集合的除法操作，对集合[2,3,4], 得到1/2/3/4，我们显然要使用左折叠——
| function arrDiv(lst) {
function div(a, b) { return a / b }
return foldl(div, 1, lst)
}
|
但折叠操作可不止这点能耐！假如这里的二元操作符左右两边类型不同呢？考虑下面的代码——
| function magic(lst) {
function addFirst(lst, elem) { return [elem, ...lst] }
return foldl(addFirst, [], lst)
}
|
magic([1,2,3])是什么结果？推导下便知。
| magic([1,2,3])
=> foldl(addFirst, [], [1,2,3])
=> [] >=> 1 >=> 2 >=> 3
=> [1] >=> 2 >=> 3
=> [2, 1] >=> 3
=> [3, 2, 1]
|
可以注意到，对于左折叠，结果的类型同折叠函数的第一个（左边的）参数相同，这个参数一般命名为 acc，意为累加；对于右折叠，结果的类型则同第二个相同了。折叠函数的参数顺序结合这里的表示方法是容易理解的。
js 中的折叠操作
js 中为数组（Array）提供了 reduce 和 reduceRight 方法，API 介绍可以看 这里，其中 reduce 代表左折叠，reduceRight 代表右折叠。
同时，对这两个方法，初始值可以不给定，这时 js 会选择使用第一个或最后一个元素作为初始值。但是不给定初始值的折叠操作对于空数组会抛出异常，这在某些时候不是我们所期望的。而且如果不给定初始值，则返回值必须是该数组中的类型，除非你想给人造成一点惊喜。
需注意的是，reduceRight 方法接受的折叠函数的参数里，acc 在前，x 在后，同 reduce 方法一致，这和上面编写的 foldr 不同。
示例
上面的描述或许仍显抽象，唯一的方式是拿更多的例子来进行推导，在实践中出真知。下面的示例中一概使用 js 的 reduce 进行描述。
map, filter, flatMap
先来点开胃菜，通过 reduce 实现 map，filter，flatMap，这几个比较简单。
| function map(fn, lst) {
return lst.reduce((acc, x) => [...acc, fn(x)], [])
}
function filter(predicate, lst) {
return lst.reduce((acc, x) => predicate(x) ? [...acc, x] : acc, [])
}
function flatMap(fn, lst) {
return lst.reduce((acc, x) => [...acc, ...fn(x)], [])
}
|
下面仅推导一下 filter。
| // 检查是否奇数
const isOdd = x => x % 2 === 1
filter(isOdd, [1,2,3,4])
=> [1, 2, 3, 4].reduce(..., [])
=> [] >=> 1 >=> 2 >=> 3 >=> 4
=> [1] >=> 2 >=> 3 >=> 4 // 1 是奇数，被添加到尾部
=> [1] >=> 3 >=> 4 // 2 不是奇数，被省略
=> [1, 3] >=> 4
=> [1, 3]
|
为什么 reduce 操作能构造 map，filter 等操作呢？因为 map，filter 等操作生成新集合，而 reduce 操作生成一个值——值这个概念显然是比集合更加广泛的。
groupBy
groupBy 函数负责将元素按特定标识符进行分组，比如将一个学生列表按班级进行分组——
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| const studentList =
[{"name" : "John", "clazz" : "101"},
{"name" : "Wick", "clazz" : "102"},
{"name" : "Neo", "clazz" : "101"},
{"name" : "Prophet", "clazz" : "102"},
{"name" : "Anderson", "clazz" : "103"},
{"name" : "Smith", "clazz" : "101"}]
function groupBy(keyMapFn, lst) {
return lst.reduce((acc, x) => {
const key = keyMapFn(x)
if (!acc.has(key)) acc.set(key, [])
acc.get(key).push(x)
return acc
}, new Map())
}
console.log(groupBy(stud=>stud.clazz, studentList))
|
推导过程如下——
| groupBy(stud=>stud.clazz, studentList)
=> lst.reduce(..., new Map())
=> {} >=> {"John" , "101"} >=> {"Wick", "102"} >=> {"Neo","101"} >=> ...
=> { 101 -> [{"John" , "101"}] } >=> {"Wick", "102"} >=> {"Neo","101"} >=> ...
=> { 101 -> [{"John" , "101"}], 102 -> [{"Wick", "102"}] } >=> {"Neo","101"} >=> ...
=> { 101 -> [{"John" , "101"}, {"Neo","101"}] , 102 -> [{"Wick", "102"}] } >=> ...
// 写不下了！
|
last, butLast
如同 last 这样的函数也能够通过 fold 实现。
|
function last(lst) {
return lst.reduce((acc, x) => x)
}
function butLast(lst) {
return lst.reduce(([a, b], x) => [b, x], ["empty list", "singleton list"]) [0]
}
|
| butLast([1,2,3])
=> [1,2,3].reduce(..., ["empty list", "singleton list"])[0]
=> (["empty list", "singleton list"] >=> 1 >=> 2 >=> 3) [0]
=> (["singleton list", 1] >=> 2 >=> 3) [0]
=> ([1, 2] >=> 3) [0]
=> [2, 3] [0]
=> 2
|
compose
将一个函数数组组合成一个函数，即类似这样[f, g, h] -> (x => f(g(h(x))))，这种操作很 trick，只有弱类型语言才办得到。compose 函数要结合柯里化函数来使用才能发挥效果。
| function compose(fnLst) {
return input => fnLst.reduceRight((acc, x) => x(acc), input)
}
|
| const toUpper = str => str.toUpperCase()
const removeChar = removedChar => str => str.replaceAll(removedChar, "")
compose([toUpper, removeChar("h")])("hello, happy world!")
=> [toUpper, removeChar("h")].reduceRight(..., "hello, happy world!")
=> toUpper >=> remoreChar("h") >=> "hello, happy world!"
=> toUpper >=> "ello, appy world"
=> "ELLO, APPY WORLD"
|
总之，我认为这种形式对于理解和使用折叠操作都是有很大帮助的，将来必可活用于实践中。