Reduce
January 23, 2022在〈Pattern matching〉看過這個範例：
def leng(lt):
match lt:
case []:
return 0
case [_, *tail]:
return 1 + leng(tail)
reduce 歸納
如果想對一個 list 計數，可以使用這個 leng 函式，如果想計算 list 中的數值乘積呢？
def product(lt):
match lt:
case []:
return 1
case [head, *tail]:
return head * product(tail)
流程上感覺有重複性，然而又好像比較難抽取出來？把遞迴函式用 f，而流程中不同的部份用 _xxx 表示呢？
def f(lt):
match lt:
case []:
return init_xxx
case [head, *tail]:
return head opt_xxx f(tail)
init_xxx 是 [] 的傳回值，head 與 f(tail) 是 opt_xxx 運算的運算元（leng 中看來沒使用 head，不過可視為給 head 而不理會罷了），如果 opt_xxx 可以使用函式指定，那麼會變成：
def reduce_right(reducer, lt, initializer):
match lt:
case []:
return initializer
case [head, *tail]:
acc = reduce_right(reducer, tail, initializer) # f(tail) 部份
return reducer(head, acc)
這麼一來，leng 與 product 可以這麼計算：
lt = [1, 2, 3, 4, 5]
leng = reduce_right(lambda elem, acc: 1 + acc, lt, 0)
product = reduce_right(lambda elem, acc: elem * acc, lt, 1)
簡單來說，reduce_right 是個流程的高階抽象，當你面對一組資料，想將其歸納為一個結果，可以考量歸納的初值、歸納過程的運算方式，而不是想著迴圈該怎麼做，這類抽象有時也稱為 fold，因為就像折紙一樣，一邊折紙，一邊進行運算，例如，若想對 [1, 2, 3, 4, 5] 加總：
lt = [1, 2, 3, 4, 5]
sum = reduce_right(lambda elem, acc: elem + acc, lt, 0)
根據方才的 reduce_right 實作，過程就像是以下：
1 + (2 + (3 + (4 + (5 + 0)))
1 + (2 + (3 + (4 + 5)))
1 + (2 + (3 + 9))
1 + (2 + 12)
1 + 14
15
這就是為什麼它會被稱為 reduce_right 的原因，從右開始往左折；相對地，也可以從左開始往右折：
def reduce(reducer, lt, initializer):
match lt:
case []:
return initializer
case [*init, last]:
acc = reduce(reducer, init, initializer)
return reducer(acc, last)
若想對 [1, 2, 3, 4, 5] 加總：
lt = [1, 2, 3, 4, 5]
sum = reduce(lambda acct, elem: acct + elem, lt, 0)
可以留意到 lambda 接受的參數，與方才的 reduce_right 是相反的，目的在反映折疊（或歸納）的方向；根據方才的 reduce 實作，過程就像是以下：
((((0 + 1) + 2) + 3) + 4) + 5
(((1 + 2) + 3) + 4) + 5
((3 + 3) + 4) + 5
(6 + 4) + 5
10 + 5
15
回到命令式
Python 就內建了 functools.reduce，例如求乘積可以如下：
from functools import reduce
lt = [1, 2, 3, 4, 5]
product = reduce(lambda acc, elem: acc * elem, lt, 1)
就命令式的角度來看，API 文件上是說，類似以下的實作：
def reduce(function, iterable, initializer=None):
it = iter(iterable)
if initializer is None:
value = next(it)
else:
value = initializer
for element in it:
value = function(value, element)
return value
也就是說，指定的函式第一個參數，會接收累計結果，第二個參數會接受元素值，有提供 reduce 這類概念的語言或程式庫，通常會採用這種慣例，以反映折疊（或歸納）的方向。
例如 JavaScript：
const product = [1, 2, 3, 4, 5]
.reduce((acc, elem) => acc * elem, 1);
不過還是要查文件，以上範例由左而右最後走訪的會是 5，以下範例由右而左最後走訪的會是 1，然而 reduceRight 接受的箭號函式在參數上，與 reduce 接受的箭號函式相同：
const product = [1, 2, 3, 4, 5]
.reduceRight((acc, elem) => acc * elem, 1);
另外要留意初值怎麼指定，例如，Java 的 Stream API，reduce 的初值是在第一個參數指定：
var product = List.of(1, 2, 3, 4, 5)
.stream()
.reduce(1, (acc, elem) -> acc * elem);
如果 API 沒有明確地指出是往右還是往左折，或者可以從非特定來源取得元素進行 reduce，指定的函式要具有結合律（Associativity），指定的初值必須是該函式的恒等值（Identity），原因可以參考 Monoid。
方才談過了，reduce 這類概念是流程的高階抽象，當你面對一組資料，想將其歸納為一個結果，可以考量歸納的初值、歸納過程的運算方式，甚至是想把一個二維結構的 list，展平為一維的 list：
from functools import reduce
lt = [[1, 3], [2, 5], [8, 9]]
flatten = reduce(lambda acc, elem: acc + elem, lt, [])
print(flatten) # [1, 3, 2, 5, 8, 9]
Python 將 reduce 歸到 functools 模組，是因為社群認為，這個高階抽象相對於 map、filter 來說，比較不好懂一些，用也不是不行，然而建議封裝為一個比較具體的名稱。例如：
from functools import reduce
def flatten(lt):
return reduce(lambda acc, elem: acc + elem, lt, [])
lt = [[1, 3], [2, 5], [8, 9]]
print(flatten(lt)) # [1, 3, 2, 5, 8, 9]
當然，這是看開發者，如果開發者熟悉函數式，應該是不會覺得不好懂啦！當你面對一組資料，想將其歸納為一個結果，可以考量歸納的初值、歸納過程的運算方式，而不是考慮迴圈。
畢竟，就 sum、leng、product、flatten 等操作而言，寫成迴圈，就算任務精簡，其實本身也比較難看出流程中的共用部份了，如果你又想順便在迴圈中做東做西的，就更難重構出可重用的抽象了。
可以 reduce 的來源並不限於 list，也可能是樹狀結構等其他類型，例如，Java 的 Collection 具有 stream 方法可以建立 Stream，後續可以進行 reduce 操作，這表示 TreeSet 等結構，也是作為 reduce 來源，因此 reduce 可以再抽象化為指定 b -> a -> b 函式與 b，將 f a 轉換為 b（f 代表 list、樹狀等類型），這種再度抽象化後的概念，在 Haskell 使用型態類別 Foldable 規範。
