I'd like a function runningSum
on an array of numbers a (or any ordered collection of addable things) that returns an array of the same length where each element i
is the sum of all elements in A up to an including i
.
Examples:
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]
I can do this with a for loop, or whatever. Is there a more functional option? It's a little like a reduce, except that it builds a result array that has all the intermediate values.
Even more general would be to have a function that takes any sequence and provides a sequence that's the running total of the input sequence.
reduce(_:_:) Returns the result of combining the elements of the sequence using the given closure.
We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]) . Return the running sum of nums . Example 1: Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
The general combinator you're looking for is often called scan
, and can be defined (like all higher-order functions on lists) in terms of 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)]
})
}
}
(But I would suggest that that's not a very good implementation.)
This is a very useful general function, and it's a shame that it's not included in the standard library.
You can then generate your cumulative sum by specializing the starting value and operation:
let cumSum = els.scan(0, +)
And you can omit the zero-length case rather simply:
let cumSumTail = els.scan(0, +).dropFirst()
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With