Add reductions(_:_:) (#46)

* Add scan function * Add initial conditional conformances to Collection and BidirectionalCollection * Rename scan to reductions * Add information to the readme about the reductions name * Add eager API * Remove Reductions' conformance to BidirectionalCollection * Implement Reductions subscript such that it occurs in constant time * Add a variant which includes the given initial result * Add a variant which takes no initial result value * Add excluding label to show the initial result is not included * Test lazy implementations * Remove reductions(including:_:) * Add conformance to LazySequenceProtocol and LazyCollectionProtocol when the base sequence conforms * Fix implementation of lazy reductions * Add test cases for sequences with one element * Tidy up tests * Improve ergonomics of no initial value eager reductions call and provide it as an extension on Sequence * Add lazy InclusiveReductions sequence * Rename Reductions to ExclusiveReductions * Add Collection implementation for InclusiveReductions * Update guide * Add links for C++ implementations * Add conformance to Collection for ExclusiveReductions * Improve ergonomics of ExclusiveReductions' index representation * Improve ergonomics of InclusiveReductions' index representation by sharing the Index implementation * Tidy up internal function * Add exclusive eager version of reductions(into:_:) * Use new lazy assertion functions * Correct the complexity claims for reductions * Separate the index types This will allow for future changes to either implementation without causing a breakage for the other. * Update guide to reflect that arrays are returned directly * Add scan as deprecated methods * Add lazy overload of reductions(into:_:) * Add the reductions(into:_:) functions * More succinctly introduce reductions * Add a note about the deprecated scan functions * Update documentation * Add @inlinable and @usableFromInline * Copy documentation to all variants of reductions * Test the value after the function is complete * Just use the += operator * Add an example for reductions(into:_:) * Improve the documentation of the return value * Update complexity note * Use the reduce documentation for inspiration for the discussion of reductions
apple · Mar 24, 2021 · b171b81 · b171b81
1 parent e652f01
commit b171b81
Show file tree

Hide file tree

Showing 4 changed files with 901 additions and 0 deletions.
diff --git a/Guides/Reductions.md b/Guides/Reductions.md
@@ -0,0 +1,139 @@
+# Reductions
+
+[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/Reductions.swift) |
+ [Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/ReductionsTests.swift)]
+
+Produces a sequence of values.
+
+This has the behaviour of reduce, but also returns all intermediate results.
+
+```swift
+let exclusiveRunningTotal = (1...5).reductions(0, +)
+print(exclusiveRunningTotal)
+// prints [0, 1, 3, 6, 10, 15]
+
+var value = 0
+let intoRunningTotal = (1...5).reductions(into: &value, +=)
+print(intoRunningTotal)
+// prints [0, 1, 3, 6, 10, 15]
+print(value)
+// prints 15
+
+let inclusiveRunningTotal = (1...5).reductions(+)
+print(inclusiveRunningTotal)
+// prints [1, 3, 6, 10, 15]
+```
+
+## Detailed Design
+
+One trio of methods are added to `LazySequenceProtocol` for a lazily evaluated
+sequence and another trio are added to `Sequence` which are eagerly evaluated.
+
+```swift
+extension LazySequenceProtocol {
+
+  public func reductions<Result>(
+    _ initial: Result,
+    _ transform: @escaping (Result, Element) -> Result
+  ) -> ExclusiveReductions<Result, Self>
+
+  public func reductions<Result>(
+    into initial: inout Result,
+    _ transform: @escaping (inout Result, Element) -> Void
+  ) -> ExclusiveReductions<Result, Self>
+
+  public func reductions(
+    _ transform: @escaping (Element, Element) -> Element
+  ) -> InclusiveReductions<Self>
+}
+```
+
+```swift
+extension Sequence {
+
+  public func reductions<Result>(
+    _ initial: Result, 
+    _ transform: (Result, Element) throws -> Result
+  ) rethrows -> [Result]
+
+  public func reductions<Result>(
+    into initial: inout Result,
+    _ transform: (inout Result, Element) throws -> Void
+  ) rethrows -> [Result]
+
+  public func reductions(
+    _ transform: (Element, Element) throws -> Element
+  ) rethrows -> [Element]
+}
+```
+
+### Complexity
+
+Calling the lazy methods, those defined on `LazySequenceProtocol`, is O(_1_).
+Calling the eager methods, those returning an array, is O(_n_).
+
+### Naming
+
+While the name `scan` is the term of art for this function, it has been 
+discussed that `reductions` aligns better with the existing `reduce` function 
+and will aid newcomers that might not know the existing `scan` term. 
+
+Deprecated `scan` methods have been added for people who are familiar with the
+term, so they can easily discover the `reductions` methods via compiler
+deprecation warnings.
+
+Below are two quotes from the Swift forum [discussion about SE-0045][SE-0045] 
+which proposed adding `scan` to the standard library and one from
+[issue #25][Issue 25] on the swift-algorithms GitHub project. These provide
+the reasoning to use the name `reductions`.
+
+[Brent Royal-Gordon][Brent_Royal-Gordon]:
+> I really like the `reduce`/`reductions` pairing instead of `reduce`/`scan`;
+it does a really good job of explaining the relationship between the two
+functions.
+
+[David Rönnqvist][David Rönnqvist]:
+> As other have already pointed out, I also feel that `scan` is the least
+intuitive name among these and that the `reduce`/`reductions` pairing would do
+a good job at explaining the relation between the two.
+
+[Kyle Macomber][Kyle Macomber]:
+> As someone unfamiliar with the prior art, `reductions` strikes me as very
+approachable—I feel like I can extrapolate the expected behavior purely from my
+familiarity with `reduce`.
+
+As part of early discussions, it was decided to have two variants, one which
+takes an initial value to use for the first element in the returned sequence, 
+and another which uses the first value of the base sequence as the initial
+value. C++ calls these variants exclusive and inclusive respectively and so 
+these terms carry through as the name for the lazy sequences; 
+`ExclusiveReductions` and `InclusiveReductions`.
+
+[SE-0045]: https://forums.swift.org/t/review-se-0045-add-scan-prefix-while-drop-while-and-iterate-to-the-stdlib/2382
+[Issue 25]: https://github.com/apple/swift-algorithms/issues/25
+[Brent_Royal-Gordon]: https://forums.swift.org/t/review-se-0045-add-scan-prefix-while-drop-while-and-iterate-to-the-stdlib/2382/6
+[David Rönnqvist]: https://forums.swift.org/t/review-se-0045-add-scan-prefix-while-drop-while-and-iterate-to-the-stdlib/2382/8
+[Kyle Macomber]: https://github.com/apple/swift-algorithms/issues/25#issuecomment-709317894
+
+### Comparison with other langauges
+
+**C++:** As of C++17, the `<algorithm>` library includes both
+[`exclusive_scan`][C++ Exclusive] and [`inclusive_scan`][C++ Inclusive]
+functions.
+
+**[Clojure][Clojure]:** Clojure 1.2 added a `reductions` function.
+
+**[Haskell][Haskell]:** Haskell includes a `scan` function for its
+`Traversable` type, which is akin to Swift's `Sequence`.
+
+**Python:** Python’s `itertools` includes an `accumulate` method. In version
+3.3, a function paramenter was added. Version 3.8 added the optional initial
+parameter.
+
+**[Rust][Rust]:** Rust provides a `scan` function.
+
+[C++ Exclusive]: https://en.cppreference.com/w/cpp/algorithm/exclusive_scan
+[C++ Inclusive]: https://en.cppreference.com/w/cpp/algorithm/inclusive_scan
+[Clojure]: http://clojure.github.io/clojure/clojure.core-api.html#clojure.core/reductions
+[Haskell]: http://hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:scanl
+[Rust]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.scan