Swift running sum

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:

  • Set StatusBar Color for Extensions in UIActivityViewController
  • How does Apple's new programming language Swift handle blocks and asynchronous requests?
  • Xcode: Passing Information from UITableViewController to UIViewController
  • Leading zeros for Int in Swift
  • UIActivityViewController share only text
  • How can I change the font of the back button for my navigation bar?
  • 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.

    6 Solutions Collect From Internet About “Swift running sum”

    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()
    

    Just for fun: The running sum as a one-liner:

    let arr = [1, 2, 3, 4]
    
    let rs = arr.map({ () -> (Int) -> Int in var s = 0; return { (s += $0, s).1 } }())
    
    print(rs) // [1, 3, 6, 10]
    

    It does the same as the (updated) code in JAL’s answer, in particular,
    no intermediate arrays are generated.
    The sum variable is captured in an immediately-evaluated closure returning the transformation.

    Swift 4

    The general sequence case

    Citing the OP:

    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.

    Consider some arbitrary sequence (conforming to Sequence), say

    var seq = 1... // 1, 2, 3, ... (CountablePartialRangeFrom)
    

    To create another sequence which is the (lazy) running sum over seq, you can make use of the global sequence(state:next:) function:

    var runningSumSequence =
        sequence(state: (sum: 0, it: seq.makeIterator())) { state -> Int? in
        if let val = state.it.next() {
            defer { state.sum += val }
            return val + state.sum
        }
        else { return nil }
    }
    
    // Consume and print accumulated values less than 100
    while let accumulatedSum = runningSumSequence.next(),
        accumulatedSum < 100 { print(accumulatedSum) }
    // 1 3 6 10 15 21 28 36 45 55 66 78 91
    
    // Consume and print next
    print(runningSumSequence.next() ?? -1) // 120
    
    // ...
    

    If we’d like (for the joy of it), we could condense the closure to sequence(state:next:) above somewhat:

    var runningSumSequence =
        sequence(state: (sum: 0, it: seq.makeIterator())) {
            (state: inout (sum: Int, it: AnyIterator<Int>)) -> Int? in
            state.it.next().map { (state.sum + $0, state.sum += $0).0 }
    }
    

    However, type inference tends to break (still some open bugs, perhaps?) for these single-line returns of sequence(state:next:), forcing us to explicitly specify the type of state, hence the gritty ... in in the closure.

    Alternatively: custom sequence accumulator

    protocol Accumulatable {
        static func +(lhs: Self, rhs: Self) -> Self
    }
    extension Int : Accumulatable {}
    
    struct AccumulateSequence<T: Sequence>: Sequence, IteratorProtocol
    where T.Element: Accumulatable {
        var iterator: T.Iterator
        var accumulatedValue: T.Element?
    
        init(_ sequence: T) {
            self.iterator = sequence.makeIterator()
        }
    
        mutating func next() -> T.Element? {
            if let val = iterator.next() {
                if accumulatedValue == nil {
                    accumulatedValue = val
                }
                else { defer { accumulatedValue = accumulatedValue! + val } }
                return accumulatedValue
    
            }
            return nil
        }
    }
    
    var accumulator = AccumulateSequence(1...)
    
    // Consume and print accumulated values less than 100
    while let accumulatedSum = accumulator.next(),
        accumulatedSum < 100 { print(accumulatedSum) }
    // 1 3 6 10 15 21 28 36 45 55 66 78 91
    

    The specific array case: using reduce(into:_:)

    As of Swift 4, we can use reduce(into:_:) to accumulate the running sum into an array.

    let runningSum = arr
        .reduce(into: []) { $0.append(($0.last ?? 0) + $1) }
        // [2, 4, 6, 8, 10, 12]
    

    By using reduce(into:_:), the [Int] accumulator will not be copied in subsequent reduce iterations; citing the Language reference:

    This method is preferred over reduce(_:_:) for efficiency when the
    result is a copy-on-write type, for example an Array or a
    Dictionary.

    See also the implementation of reduce(into:_:), noting that the accumulator is provided as an inout parameter to the supplied closure.

    However, each iteration will still result in an append(_:) call on the accumulator array; amortized O(1) averaged over many invocations, but still an arguably unnecessary overhead here as we know the final size of the accumulator.

    Because arrays increase their allocated capacity using an exponential
    strategy, appending a single element to an array is an O(1) operation
    when averaged over many calls to the append(_:) method. When an array
    has additional capacity and is not sharing its storage with another
    instance, appending an element is O(1). When an array needs to
    reallocate storage before appending or its storage is shared with
    another copy, appending is O(n), where n is the length of the array.

    Thus, knowing the final size of the accumulator, we could explicitly reserve such a capacity for it using reserveCapacity(_:) (as is done e.g. for the native implementation of map(_:))

    let runningSum = arr
        .reduce(into: [Int]()) { (sums, element) in
            if let sum = sums.last {
                sums.append(sum + element)
            }
            else {
                sums.reserveCapacity(arr.count)
                sums.append(element)
            }
    } // [2, 4, 6, 8, 10, 12]
    

    For the joy of it, condensed:

    let runningSum = arr
        .reduce(into: []) {
            $0.append(($0.last ?? ($0.reserveCapacity(arr.count), 0).1) + $1)
    } // [2, 4, 6, 8, 10, 12]
    

    Swift 3: Using enumerated() for subsequent calls to reduce

    Another Swift 3 alternative (with an overhead …) is using enumerated().map in combination with reduce within each element mapping:

    func runningSum(_ arr: [Int]) -> [Int] {
        return arr.enumerated().map { arr.prefix($0).reduce($1, +) }
    } /* thanks @Hamish for improvement! */
    
    let arr = [2, 2, 2, 2, 2, 2]
    print(runningSum(arr)) // [2, 4, 6, 8, 10, 12]
    

    The upside is you wont have to use an array as the collector in a single reduce (instead repeatedly calling reduce).

    If you just want it to work for Int, you can use this:

    func runningSum(array: [Int]) -> [Int] {
        return array.reduce([], combine: { (sums, element) in
            return sums + [element + (sums.last ?? 0)]
        })
    }
    

    If you want it to be generic over the element type, you have to do a lot of extra work declaring the various number types to conform to a custom protocol that provides a zero element, and (if you want it generic over both floating point and integer types) an addition operation, because Swift doesn’t do that already. (A future version of Swift may fix this problem.)

    Assuming an array of Ints, sounds like you can use map to manipulate the input:

    let arr = [0,1,0,1,0,1]
    
    var sum = 0
    let val = arr.map { (sum += $0, sum).1 }
    
    print(val) // "[0, 1, 1, 2, 2, 3]\n"
    

    I’ll keep working on a solution that doesn’t use an external variable.

    One solution using reduce:

    func runningSum(array: [Int]) -> [Int] {
        return array.reduce([], combine: { (result: [Int], item: Int) -> [Int] in
            if result.isEmpty {
                return [item] //first item, just take the value
            }
    
            // otherwise take the previous value and append the new item
            return result + [result.last! + item]
        })
    }