Quick amount

Question

I need a runningSum function in an array of numbers a (or any ordered collection of extra things) that returns an array of the same length where each element i is the sum of all elements in before i included .

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? This is a bit like a shorthand, except that it creates an array of results that has all the intermediate values.

Even more common would be to have a function that takes any sequence and provides a sequence in which the total number of input sequence is executed.

Answer 1

The general combinator you are looking for is often called scan and can be defined (like all higher order functions in 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 easy to prove inductively // that this unwrapping can't fail let lastElement = listSoFar.last! return listSoFar + [f(lastElement, next)] }) } } 

(But I would say that this is not a very good implementation.)

This is a very useful general function, and it’s a shame that it is not included in the standard library.

Then you can generate your total amount by specifying the initial value and operation:

 let cumSum = els.scan(0, +) 

And you can just omit the zero-length case:

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

Answer 2

Swift 4

General case of sequence

Referring to the OP:

Even more common would be to have a function that accepts any sequence and provides a sequence in which the total amount of input to the sequence is executed.

Consider some arbitrary sequence (corresponding to Sequence ), say

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

To create another sequence that represents the (lazy) amount of execution on seq , you can use 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 wanted (for the sake of this joy), we could smooth out the short circuit to sequence(state:next:) 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 (at least some open errors, maybe?) For these single-line returns of sequence(state:next:) , forcing us to explicitly specify the state type, therefore, gritty ... in to close.

Alternative: custom sequence drive

 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 

Array specific case: using reduce(into:_:)

With Swift 4, we can use reduce(into:_:) to accumulate the current amount into an array.

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

Using reduce(into:_:) , the battery [Int] will not be copied in subsequent iteration reductions; Referring to Language Link :

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

See also the reduce(into:_:) implementation , noting that the battery is provided as an inout in the supplied closure.

However, each iteration will still lead to a call to append(_:) drive array; amortized O(1) , averaged over many calls, but still, possibly, extra overhead, since we know the final size of the battery.

As arrays increase their allocated capacity using an exponential strategy, adding one element to an array is an O(1) operation when averaging over many calls to the append(_:) method. When an array has extra capacity and does not share its storage with another instance, adding an O(1) element. When an array must redistribute the storage before adding or store it together with another copy, the addition is O(n) , where n is the length of the array.

Thus, knowing the final size of the battery, we could explicitly reserve such a capacity for it using reserveCapacity(_:) (as is done, for example, for the built-in map(_:) implementation )

 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 joy concise:

 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 reduce calls

Another Swift 3 alternative (with overhead ...) uses enumerated().map in combination with reduce in 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 surface you don’t have to use the array as a collector in a single reduce (instead, it calls reduce again).

Answer 3

Just for fun: Current amount as single line:

 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 the JAL answer , in particular, no intermediate arrays are created. The sum variable is fixed in the immediately evaluated closure returning the conversion.

Answer 4

Assuming an array of Int s, it seems like you can use map to control 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 will continue to work on a solution that does not use an external variable.

Answer 5

If you just want it to work on 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 in type of element, you need to do a lot of extra work by declaring different types of numbers to conform to the custom protocol that provides the null element, and (if you want it to be common to both floating-point types comma and integer types) add operation since Swift no longer does this. (A future version of Swift may solve this problem.)

Answer 6

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] }) }