雖然之前對折疊操作進行過一些了解，但是仍然對其不甚熟悉，沒法立刻寫出定義，最近突然發(fā)現(xiàn)一種能方便理解折疊操作的方法，這里對其進行一些記錄，使用js來進行描述。

啥子是折疊？

對集合的操作，最常用的也就那三種——map，filter，reduce/fold（后面全部使用fold）。其中，map對集合的每一個元素進行相同的映射，返回一個映射后的新集合；filter對集合中的每一個元素進行判斷，篩選出符合條件的元素組成返回的集合；而fold操作迭代一個數(shù)組，并將每個元素“積累”到同一個值中。

fold操作就是所謂的折疊操作。折疊操作是最原子的——map，filter，flatMap/bind操作都可以由它來實現(xiàn)；折疊操作也可以用于實現(xiàn)某些高層次的業(yè)務(wù)相關(guān)的操作，如count，groupBy等。

所以，究竟什么是折疊？根據(jù)折疊操作的描述，我們可以認(rèn)為那些簽名為[a] => b的函數(shù)都是折疊操作，比如我們有個sum函數(shù)，它能夠計算一個集合內(nèi)所有元素的和，這就是一個折疊操作，它的函數(shù)簽名為[number] => number。

我們規(guī)定sum(null) === 0, sum([]) === 0，容易得到sum函數(shù)的遞歸實現(xiàn)——

再考慮一個product函數(shù)，它計算一個集合內(nèi)所有元素的積，我們規(guī)定product(null) === 1, product([]) === 1，容易得到它的遞歸實現(xiàn)——

可以發(fā)現(xiàn)，這兩個函數(shù)的形式基本一致，我們可以再抽象一層，整出一個所謂的foldr函數(shù)。在這里，參數(shù)fn就是上面的sum函數(shù)的+，product函數(shù)的*，我們乘其為折疊函數(shù)，init就是初始值，對sum來說是0，對product來說是1。foldr是遞歸的折疊操作。

但我們也知道，這些函數(shù)也是能夠?qū)懗晌策f歸的形式的，這些形式能夠抽象成折疊操作嗎？答案是yes，這樣尾遞歸形式（或者就SICP的語境上來說，迭代）的折疊操作，我們稱為foldl。

顯然，在一般的語言中，foldl的性能會好于foldr，因為前者是尾遞歸形式，能夠被優(yōu)化成循環(huán)。foldr的意義在于它展開的形式和遞歸的形式是一致的，在學(xué)術(shù)上肯定有一定價值，而且在Haskell這樣的惰性求值的語言里，它的表現(xiàn)會比普通foldl好。

定義姑且是提出來了，但foldl和foldr的區(qū)別和對其的感性認(rèn)識呢？Keep going。

形象表述

一切折疊操作，都可以表示為數(shù)組中各元素連同初始值使用特定二元操作符兩兩連接的形式，而左折疊和右折疊會決定初始值的位置以及該二元操作符的結(jié)合性——對于左折疊來說，初始值在最左，該操作符左結(jié)合；對于右折疊來說，初始值在最右，該操作符右結(jié)合。下面展示一個示例。

考慮一個左折疊操作，假設(shè)初始值為100；折疊函數(shù)為>=>，我們可以叫它fish，簡稱f，1 >=> 2等價于f(1, 2)；要折疊的數(shù)組為[1, 2, 3]，我們可以這樣描述這個折疊操作——

右折疊也是如此——

這種形式如何進行推導(dǎo)呢？我們先將其轉(zhuǎn)換為使用>=>（其他符號也行）進行連接的形式，根據(jù)結(jié)合性按順序進行函數(shù)應(yīng)用。舉個小小的例子——考慮定義一個集合的除法操作，對集合[2,3,4],得到1/2/3/4，我們顯然要使用左折疊——

但折疊操作可不止這點能耐！假如這里的二元操作符左右兩邊類型不同呢？考慮下面的代碼——

magic([1,2,3])是什么結(jié)果？推導(dǎo)下便知。

可以注意到，對于左折疊，結(jié)果的類型同折疊函數(shù)的第一個（左邊的）參數(shù)相同，這個參數(shù)一般命名為acc，意為累加；對于右折疊，結(jié)果的類型則同第二個相同了。折疊函數(shù)的參數(shù)順序結(jié)合這里的表示方法是容易理解的。

js中的折疊操作

js中為數(shù)組（Array）提供了reduce和reduceRight方法，API介紹可以看 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce，其中reduce代表左折疊，reduceRight代表右折疊。

同時，對這兩個方法，初始值可以不給定，這時js會選擇使用第一個或最后一個元素作為初始值。但是不給定初始值的折疊操作對于空數(shù)組會拋出異常，這在某些時候不是我們所期望的。而且如果不給定初始值，則返回值必須是該數(shù)組中的類型（除非你想給其他程序員造成驚喜，梗見https://en.wikipedia.org/wiki/Principle_of_least_astonishment）。

需注意的是，reduceRight方法接受的折疊函數(shù)，acc在前，x在后，同reduce方法一致，這和上面編寫的foldr不同。

示例

上面的描述或許仍顯抽象，唯一的方式是拿更多的例子來進行推導(dǎo)，在實踐中出真知。下面的示例中一概使用js的reduce進行描述。

map, filter, flatMap

先來點開胃菜，通過reduce實現(xiàn)map，filter，flatMap，這幾個比較簡單。

下面僅推導(dǎo)一下filter。

為什么reduce操作能構(gòu)造map，filter等操作呢？因為map，filter等操作生成新集合，而reduce操作生成一個值——值這個概念顯然是比集合更加廣泛的。

groupBy

groupBy函數(shù)負(fù)責(zé)將元素按特定標(biāo)識符進行分組，比如將一個學(xué)生列表按班級進行分組——

推導(dǎo)過程如下——

last, butLast

compose

compose函數(shù)將一個函數(shù)數(shù)組組合成一個函數(shù)，其效果類似這樣[f, g, h] -> (x => f(g(h(x))))，這種操作我覺得很trick，只有弱類型語言才辦得到。compose函數(shù)要結(jié)合柯里化函數(shù)來使用才能發(fā)揮效果。

一個使用和推導(dǎo)過程見下——

總之，我認(rèn)為這種形式對于理解和使用折疊操作都是有很大幫助的，將來必可活用于實踐中。