Python 集合的归约与折叠

可以通过下面的方式定义sum()函数。
空集合的和为0，非空集合的和是第一个元素加上剩余元素组成集合的和。

类似地，以递归方式计算集合乘积分以下两种情况：

基础型式定义空集合的乘积为1。递归型式定义非空集合的乘积是第一个元素乘剩余元素组成集合的乘积。

这样就定义了序列中每个元素间加法和乘法的fold操作，并且由于是从右向左处理集合元素，可以将上面的处理过程视作以fold-righ的方式将集合归约为标量值。

可以用递归的形式使用Python计算集合的乘积，如下所示：

def prodrc(collection: Sequence[float]) -> float:
    if len(collection) == 0: return 1
    return collection[0] * prodrc(collection[1:])

直接把数学定义转换为了Python代码，从技术上看完全正确，但这个实现方法不够理想，因为计算过程中会创建大量中间列表对象，而且只能处理集合，不能处理可迭代对象。

除此之外，类型标示中使用了float，但也可以处理整型值并返回整型值。在这样的数值计算函数中，将float用作通用的类型标示更简便。

将其简单修改一下，就可以处理可迭代对象了，同时避免了创建任何中间对象。能处理迭代类型数据源的递归乘积函数如下所示：

def prodri(items: Iterator[float]) -> float:
    try:
        head = next(items)
    except StopIteration:
        return 1
    return head * prodri(items)

对可迭代对象，无法使用len()函数计算其元素数量，只能尝试从中取出第一个元素。如果其中没有元素，尝试取元素将引发StopIteration异常。如果可迭代对象中有元素，将它与序列中剩余元素的乘积相乘。为了便于理解，这里显式地用iter()函数将一个实例化的序列转换为可迭代对象。实际编码过程中如果可迭代对象直接可用，就不必再转换了，示例如下：

>>> prodri(iter([1, 2, 3, 4, 5, 6, 7]))
5040

该递归实现不依赖显式状态，以及Python的其他命令式特性。虽然是纯粹的函数式，但它仍然受限于集合大小不能超过1000。在具体的编程实践中，常用如下命令式结构实现递归函数：

def prodi(items: Iterable[float]) -> float:
    p = 1
    for n in items:
        p *= n
    return p

此版本不再受限于递归次数，实现了尾调用优化，并且能同时处理序列和可迭代对象。

在其他函数式语言中，把这个实现称为foldl（即fold-left）操作，因为它从左向右依次处理可迭代集合中的元素，与之相对的是foldr（即fold-right）操作，也就是从右向左依次处理集合中的元素。

对于实现了优化编译器和惰性求值的语言来说，fold-left和fold-right的区别在于创建中间结果的方式。这一差异会影响计算性能，但通常不太明显。fold-left首先处理序列的第一个元素，而fold-right会先取出第一个元素，但并不进行处理，而是待整个序列处理完后再处理此元素。