虽然之前对折叠操作进行过一些了解，但是仍然对其不甚熟悉，没法立刻写出定义，最近突然发现一种能方便理解折叠操作的方法，这里对其进行一些记录，使用js来进行描述。

啥子是折叠？

对集合的操作，最常用的也就那三种——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函数的递归实现——

再考虑一个product函数，它计算一个集合内所有元素的积，我们规定product(null) === 1, product([]) === 1，容易得到它的递归实现——

可以发现，这两个函数的形式基本一致，我们可以再抽象一层，整出一个所谓的foldr函数。在这里，参数fn就是上面的sum函数的+，product函数的*，我们乘其为折叠函数，init就是初始值，对sum来说是0，对product来说是1。foldr是递归的折叠操作。

但我们也知道，这些函数也是能够写成尾递归的形式的，这些形式能够抽象成折叠操作吗？答案是yes，这样尾递归形式（或者就SICP的语境上来说，迭代）的折叠操作，我们称为foldl。

显然，在一般的语言中，foldl的性能会好于foldr，因为前者是尾递归形式，能够被优化成循环。foldr的意义在于它展开的形式和递归的形式是一致的，在学术上肯定有一定价值，而且在Haskell这样的惰性求值的语言里，它的表现会比普通foldl好。

定义姑且是提出来了，但foldl和foldr的区别和对其的感性认识呢？Keep going。

形象表述

一切折叠操作，都可以表示为数组中各元素连同初始值使用特定二元操作符两两连接的形式，而左折叠和右折叠会决定初始值的位置以及该二元操作符的结合性——对于左折叠来说，初始值在最左，该操作符左结合；对于右折叠来说，初始值在最右，该操作符右结合。下面展示一个示例。

考虑一个左折叠操作，假设初始值为100；折叠函数为>=>，我们可以叫它fish，简称f，1 >=> 2等价于f(1, 2)；要折叠的数组为[1, 2, 3]，我们可以这样描述这个折叠操作——

右折叠也是如此——

这种形式如何进行推导呢？我们先将其转换为使用>=>（其他符号也行）进行连接的形式，根据结合性按顺序进行函数应用。举个小小的例子——考虑定义一个集合的除法操作，对集合[2,3,4],得到1/2/3/4，我们显然要使用左折叠——

但折叠操作可不止这点能耐！假如这里的二元操作符左右两边类型不同呢？考虑下面的代码——

magic([1,2,3])是什么结果？推导下便知。

可以注意到，对于左折叠，结果的类型同折叠函数的第一个（左边的）参数相同，这个参数一般命名为acc，意为累加；对于右折叠，结果的类型则同第二个相同了。折叠函数的参数顺序结合这里的表示方法是容易理解的。

js中的折叠操作

js中为数组（Array）提供了reduce和reduceRight方法，API介绍可以看 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce，其中reduce代表左折叠，reduceRight代表右折叠。

同时，对这两个方法，初始值可以不给定，这时js会选择使用第一个或最后一个元素作为初始值。但是不给定初始值的折叠操作对于空数组会抛出异常，这在某些时候不是我们所期望的。而且如果不给定初始值，则返回值必须是该数组中的类型（除非你想给其他程序员造成惊喜，梗见https://en.wikipedia.org/wiki/Principle_of_least_astonishment）。

需注意的是，reduceRight方法接受的折叠函数，acc在前，x在后，同reduce方法一致，这和上面编写的foldr不同。

示例

上面的描述或许仍显抽象，唯一的方式是拿更多的例子来进行推导，在实践中出真知。下面的示例中一概使用js的reduce进行描述。

map, filter, flatMap

先来点开胃菜，通过reduce实现map，filter，flatMap，这几个比较简单。

下面仅推导一下filter。

为什么reduce操作能构造map，filter等操作呢？因为map，filter等操作生成新集合，而reduce操作生成一个值——值这个概念显然是比集合更加广泛的。

groupBy

groupBy函数负责将元素按特定标识符进行分组，比如将一个学生列表按班级进行分组——

推导过程如下——

last, butLast

compose

compose函数将一个函数数组组合成一个函数，其效果类似这样[f, g, h] -> (x => f(g(h(x))))，这种操作我觉得很trick，只有弱类型语言才办得到。compose函数要结合柯里化函数来使用才能发挥效果。

一个使用和推导过程见下——

总之，我认为这种形式对于理解和使用折叠操作都是有很大帮助的，将来必可活用于实践中。