Should we have a sequence that vends the running total of a Sequence.reduce call? This would be like C++'s std::partial_sum (or std::iota):
/// An iterator for implementing the progressive combination of wrapped elements by a reduction closure.
struct ProgressivelyReduceImplementationIterator<Base: IteratorProtocol> {
/// The iterator for the operands.
var base: Base
/// The last result calculated.
var last: Base.Element?
/// The closure for reducing operands into the result.
let reducer: (Base.Element, Base.Element) throws -> Base.Element
/// The error that ended iteration, if that happened. `nil` if no throw has occurred / did occur.
private(set) var endingError: Error?
/// Creates an iterator that vends reductions over elements of the given iteator using the given closure.
init(_ base: Base, reducingBy nextPartialResult: @escaping (Base.Element, Base.Element) throws -> Base.Element ) {
self.base = base
last = nil
reducer = nextPartialResult
endingError = nil
}
}
extension ProgressivelyReduceImplementationIterator: IteratorProtocol {
mutating func next() -> Result<Base.Element, Error>? {
guard endingError == nil else { return nil }
guard let nextBase = base.next() else { return nil }
guard let lastResult = last else {
last = nextBase
return .success(last!)
}
do {
last = try reducer(lastResult, nextBase)
return .success(last!)
} catch {
endingError = error
return .failure(error)
}
}
}
extension Sequence {
public func progressivelyReduce<T: RangeReplaceableCollection>(storingAs: T.Type, by nextPartialResult: (Element, Element) throws -> Element) throws -> T where T.Element == Element {
return try withoutActuallyEscaping(nextPartialResult) {
return T(try IteratorSequence(ProgressivelyReduceImplementationIterator(makeIterator(), reducingBy: $0)).lazy.map { r in try r.get() })
}
}
public func progressivelyReduce(by nextPartialResult: (Element, Element) throws -> Element) throws -> [Element] {
return try progressivelyReduce(storingAs: Array.self, by: nextPartialResult)
}
public func progressivelyReduce<T: RangeReplaceableCollection>(storingAs: T.Type, by nextPartialResult: (Element, Element) -> Element) -> T where T.Element == Element {
return withoutActuallyEscaping(nextPartialResult) {
return T(IteratorSequence(ProgressivelyReduceImplementationIterator(makeIterator(), reducingBy: $0)).lazy.map { r in try! r.get() })
}
}
public func progressivelyReduce(by nextPartialResult: (Element, Element) -> Element) -> [Element] {
return progressivelyReduce(storingAs: Array.self, by: nextPartialResult)
}
}
/// A sequence for the progressive combination of wrapped elements by a reduction closure.
public struct LazyProgressivelyReducingSequence<Base: Sequence> {
/// The sequence for the operands.
let base: Base
/// The closure for reducing operands into the result.
let reducer: (Base.Element, Base.Element) -> Base.Element
}
extension LazyProgressivelyReducingSequence {
public struct Iterator {
/// The iterator doing all the work.
var iterator: ProgressivelyReduceImplementationIterator<Base.Iterator>
}
}
extension LazyProgressivelyReducingSequence.Iterator: IteratorProtocol {
public mutating func next() -> Base.Element? {
return try! iterator.next()?.get()
}
}
extension LazyProgressivelyReducingSequence: Sequence {
public __consuming func makeIterator() -> Iterator {
return Iterator(iterator: ProgressivelyReduceImplementationIterator(base.makeIterator(), reducingBy: reducer))
}
public var underestimatedCount: Int { return base.underestimatedCount }
}
extension LazyProgressivelyReducingSequence: LazySequenceProtocol {}
extension LazySequenceProtocol {
public func progressivelyReduce(by nextPartialResult: @escaping (Element, Element) -> Element) -> LazyProgressivelyReducingSequence<Elements> {
return LazyProgressivelyReducingSequence(base: elements, reducer: nextPartialResult)
}
}
extension LazyProgressivelyReducingSequence: Collection where Base: Collection {
public struct Index: Comparable {
/// The location of the target element.
let index: Base.Index
/// A cache of the element's progressive reduction.
let reduction: Base.Element?
public static func == (lhs: Index, rhs: Index) -> Bool {
return lhs.index == rhs.index
}
public static func < (lhs: Index, rhs: Index) -> Bool {
return lhs.index < rhs.index
}
}
public var startIndex: Index { return Index(index: base.startIndex, reduction: base.first) }
public var endIndex: Index { return Index(index: base.endIndex, reduction: nil) }
public subscript(position: Index) -> Base.Element { return position.reduction! }
public func index(after i: Index) -> Index {
precondition(i.index < base.endIndex)
let nextBaseIndex = base.index(after: i.index)
return Index(index: nextBaseIndex, reduction: nextBaseIndex == base.endIndex ? nil : reducer(i.reduction!, base[nextBaseIndex]))
}
/*
BidirectionalCollection is out because it requires figuring out the total reduction when calculating endIndex, which would make it O(n) each time. The dependence on the neighbor's result when calculating the next one precludes RandomAccessCollection support.
*/
}
extension LazyProgressivelyReducingSequence.Index: Hashable where Base: Collection, Base.Index: Hashable {
public func hash(into hasher: inout Hasher) {
index.hash(into: &hasher)
}
}
/// A collection of the progression of wrapped elements under a reduction closure.
typealias LazyProgressiveReducingCollection<Base: Collection> = LazyProgressivelyReducingSequence<Base>
extension LazyProgressiveReducingCollection: LazyCollectionProtocol {}
let numbers = [1, 2, 3, 4]
let numberSum = numbers.reduce(0, +) // 10
let triangleNumbers = numbers.progressivelyReduce(by: +) // [1, 3, 6, 10]
let lazyTriangleNumbers = numbers.lazy.progressivelyReduce(by: +)
Array(lazyTriangleNumbers) // [1, 3, 6, 10]
numbers[numbers.endIndex..<numbers.endIndex].progressivelyReduce(by: +) // []
Array(numbers[numbers.endIndex..<numbers.endIndex].lazy.progressivelyReduce(by: +)) // []
numbers[1..<2].progressivelyReduce(by: +) // [2]
Array(numbers[1..<2].lazy.progressivelyReduce(by: +)) // [2]
let lazyTriangleNumbers2 = lazyTriangleNumbers.indices.map { lazyTriangleNumbers[$0] } // [1, 3, 6, 10]
The code above requires Swift 5.