快速运行总和

我想要一个函数runningSum在数字数组 a （或任何可添加事物的有序集合）上，返回相同长度的数组，其中每个元素i是 A 中所有元素的总和最多包括i.

例子：

runningSum([1,1,1,1,1,1]) -> [1,2,3,4,5,6]
runningSum([2,2,2,2,2,2]) -> [2,4,6,8,10,12]
runningSum([1,0,1,0,1,0]) -> [1,1,2,2,3,3]
runningSum([0,1,0,1,0,1]) -> [0,1,1,2,2,3]

我可以用 for 循环或者其他什么来做到这一点。有更实用的选择吗？它有点像归约，只不过它构建了一个包含所有中间值的结果数组。

更一般的是有一个函数可以接受任何序列并提供一个序列，该序列是输入序列的运行总计。

您正在寻找的通用组合器通常称为scan https://en.wikipedia.org/wiki/Prefix_sum#Scan_higher_order_function，并且可以定义为（像列表上的所有高阶函数一样）reduce:

extension Array {
    func scan<T>(initial: T, _ f: (T, Element) -> T) -> [T] {
        return self.reduce([initial], combine: { (listSoFar: [T], next: Element) -> [T] in
            // because we seeded it with a non-empty
            // list, it's easy to prove inductively
            // that this unwrapping can't fail
            let lastElement = listSoFar.last!
            return listSoFar + [f(lastElement, next)]
        })
    }
}

（但我认为这不是一个很好的实现。）

这是一个非常有用的通用函数，遗憾的是它没有包含在标准库中。

然后，您可以通过专门化起始值和运算来生成累积和：

let cumSum = els.scan(0, +)

您可以相当简单地省略零长度的情况：

let cumSumTail = els.scan(0, +).dropFirst()