快速运行总和

Question

我想要一个函数 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 循环或其他任何方式来完成此操作。有没有更实用的选择？它有点像 reduce，只是它构建了一个包含所有中间值的结果数组。

更一般的做法是拥有一个接受任何序列并提供一个序列的函数，该序列是输入序列的运行总和。

Answer 1

您正在寻找的通用组合器通常称为 scan ，并且可以根据 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()