当我们对列表求和时，我们指定一个累加器 ( memo)，然后遍历列表，将二进制函数“x+y”应用于每个元素和累加器。在程序上，这看起来像：
def mySum(list):
memo = 0
for e in list:
memo = memo + e
return memo
这是一种常见的模式，对求和以外的其他事情很有用——我们可以将它推广到任何二进制函数，我们将提供它作为参数，并让调用者指定一个初始值。这为我们提供了一个称为reduce、foldl或inject[1]的函数：
def myReduce(function, list, initial):
memo = initial
for e in list:
memo = function(memo, e)
return memo
def mySum(list):
return myReduce(lambda memo, e: memo + e, list, 0)
在 Python 2 中，reduce它是一个内置函数，但在 Python 3 中，它被移到了functools模块中：
from functools import reduce
reduce根据我们作为第一个参数提供的函数，我们可以做各种很酷的事情。如果我们用“list concatenation”替换“sum”，用“empty list”替换“zero”，我们得到（浅）copy函数：
def myCopy(list):
return reduce(lambda memo, e: memo + [e], list, [])
myCopy(range(10))
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
如果我们将一个transform函数作为另一个参数添加到copy，并在连接之前应用它，我们会得到map：
def myMap(transform, list):
return reduce(lambda memo, e: memo + [transform(e)], list, [])
myMap(lambda x: x*2, range(10))
> [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
如果我们添加一个以参数为参数并返回布尔值的predicate函数e，并使用它来决定是否连接，我们得到filter：
def myFilter(predicate, list):
return reduce(lambda memo, e: memo + [e] if predicate(e) else memo, list, [])
myFilter(lambda x: x%2==0, range(10))
> [0, 2, 4, 6, 8]
map并且filter是编写列表推导式的一种奇怪的方式——我们也可以说[x*2 for x in range(10)]or [x for x in range(10) if x%2==0]. 没有对应的列表解析语法reduce，因为reduce根本不需要返回列表（正如我们在sum前面看到的，Python 也恰好作为内置函数提供）。
事实证明，对于计算运行总和，列表构建能力reduce正是我们想要的，并且可能是解决这个问题的最优雅的方法，尽管它（与 一起lambda）被认为是一种非 Python 式的陈词滥调。该版本在reduce运行时会留下其旧值的副本，称为reductionsor scanl[1]，它看起来像这样：
def reductions(function, list, initial):
return reduce(lambda memo, e: memo + [function(memo[-1], e)], list, [initial])
如此装备，我们现在可以定义：
def running_sum(list):
first, rest = list[0], list[1:]
return reductions(lambda memo, e: memo + e, rest, first)
running_sum(range(10))
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
虽然在概念上很优雅，但这种精确的方法在 Python 的实践中表现不佳。因为 Python 会list.append()在原地改变一个列表但不返回它，所以我们不能在 lambda 中有效地使用它，而必须使用+运算符。这构造了一个全新的列表，它所花费的时间与迄今为止累积列表的长度成正比（即 O(n) 操作）。由于我们已经在执行此操作的 O(n)for循环中reduce，因此总体时间复杂度为 O(n 2 )。
在像 Ruby [2]这样array.push e返回 mutated的语言中array，等效的运行时间为 O(n)：
class Array
def reductions(initial, &proc)
self.reduce [initial] do |memo, e|
memo.push proc.call(memo.last, e)
end
end
end
def running_sum(enumerable)
first, rest = enumerable.first, enumerable.drop(1)
rest.reductions(first, &:+)
end
running_sum (0...10)
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
同样在 JavaScript [2]中，它的array.push(e)返回e（不是array），但它的匿名函数允许我们包含多个语句，我们可以使用它们来分别指定一个返回值：
function reductions(array, callback, initial) {
return array.reduce(function(memo, e) {
memo.push(callback(memo[memo.length - 1], e));
return memo;
}, [initial]);
}
function runningSum(array) {
var first = array[0], rest = array.slice(1);
return reductions(rest, function(memo, e) {
return x + y;
}, first);
}
function range(start, end) {
return(Array.apply(null, Array(end-start)).map(function(e, i) {
return start + i;
}
}
runningSum(range(0, 10));
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
那么，我们怎样才能解决这个问题，同时保留reductions我们刚刚传递给以lambda x, y: x + y创建运行求和函数的函数的概念简单性呢？让我们按程序重写reductions。我们可以解决意外的二次问题，并且在处理它的同时，预先分配结果列表以避免堆抖动[3]：
def reductions(function, list, initial):
result = [None] * len(list)
result[0] = initial
for i in range(len(list)):
result[i] = function(result[i-1], list[i])
return result
def running_sum(list):
first, rest = list[0], list[1:]
return reductions(lambda memo, e: memo + e, rest, first)
running_sum(range(0,10))
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
这是我的最佳选择：O(n) 性能，并且优化的过程代码隐藏在一个有意义的名称下，下次您需要编写一个将中间值累积到列表中的函数时可以重新使用它。
- 名称
reduce/reductions来自 LISP 传统，foldl/scanl来自 ML 传统，以及inject来自 Smalltalk 传统。
- Python
List和 RubyArray都是自动调整大小的数据结构的实现，称为“动态数组”（或std::vector在 C++ 中）。JavaScriptArray有点巴洛克风格，但只要您不分配给越界索引或 mutate ，其行为就会相同Array.length。
- 每当列表的长度超过 2 的幂时，在 Python 运行时中形成列表后备存储的动态数组将自行调整大小。调整列表大小意味着在两倍于旧列表大小的堆上分配一个新列表，将旧列表的内容复制到新列表中，并将旧列表的内存返回给系统。这是一个 O(n) 操作，但由于随着列表变得越来越大，它发生的频率越来越低，附加到列表的时间复杂度在平均情况下为 O(1)。但是，旧列表留下的“洞”有时可能难以回收，具体取决于它在堆中的位置。即使使用垃圾收集和强大的内存分配器，预先分配已知大小的数组也可以为底层系统节省一些工作。