Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Swift running sum

Tags:

swift

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.

like image 601
Benjohn Avatar asked Feb 02 '16 18:02

Benjohn


People also ask

What is reduce in Swift?

reduce(_:_:) Returns the result of combining the elements of the sequence using the given closure.

What is running array sum?

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].


1 Answers

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()
like image 76
Ian Henry Avatar answered Sep 20 '22 22:09

Ian Henry