A running reduce?

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.

I’m not entirely sure where the term comes from but I’ve heard of scan being used to refer to this method.

This was brought up in a thread a while back and I’ll just post a link to the last reply from there:

Since it was already pitched and rejected, you’d need to provide more of an explanation for why you think this should be in the standard library.

2 Likes

I think naming it is difficult and something like progressivelyReduce would be a much better name than previously seen. I'm not sure where the name scan comes from, but I don't think it tells the caller what the function does at all, and I think accumulate sounds like it would do the same thing as reduce. runningSum might explain it, but it wouldn't be consistent with reduce.

Terms of Service

Privacy Policy

Cookie Policy