# Reduce

January 23, 2022

``````def leng(lt):
match lt:
case []:
return 0
case [_, *tail]:
return 1 + leng(tail)
``````

## reduce 歸納

``````def product(lt):
match lt:
case []:
return 1
``````

``````def f(lt):
match lt:
case []:
return init_xxx
``````

init_xxx 是 `[]` 的傳回值，head 與 f(tail) 是 opt_xxx 運算的運算元（`leng` 中看來沒使用 `head`，不過可視為給 `head` 而不理會罷了），如果 opt_xxx 可以使用函式指定，那麼會變成：

``````def reduce_right(reducer, lt, initializer):
match lt:
case []:
return initializer
acc = reduce_right(reducer, tail, initializer) # f(tail) 部份
``````

``````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)
``````

``````lt = [1, 2, 3, 4, 5]
sum = reduce_right(lambda elem, acc: elem + acc, lt, 0)
``````

``````1 + (2 + (3 + (4 + (5 + 0)))
1 + (2 + (3 + (4 + 5)))
1 + (2 + (3 + 9))
1 + (2 + 12)
1 + 14
15
``````

``````def reduce(reducer, lt, initializer):
match lt:
case []:
return initializer
case [*init, last]:
acc = reduce(reducer, init, initializer)
return reducer(acc, last)
``````

``````lt = [1, 2, 3, 4, 5]
sum = reduce(lambda acct, elem: acct + elem, lt, 0)
``````

``````((((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)
``````

``````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
``````

``````const product = [1, 2, 3, 4, 5]
.reduce((acc, elem) => acc * elem, 1);
``````

``````const product = [1, 2, 3, 4, 5]
.reduceRight((acc, elem) => acc * elem, 1);
``````

``````var product = List.of(1, 2, 3, 4, 5)
.stream()
.reduce(1, (acc, elem) -> acc * elem);
``````

``````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]
``````