SE-0240: Ordered Collection Diffing

(Douglas Gregor) #41

There were some issues in the review that the Core Team felt sorted themselves out in the thread and don't need further discussion because the proposal as-written has the right design, such as the question of storing offsets rather than indices.

Much of this discussion here was about making the diffing algorithm more flexible, with a range of solutions from adding a policy parameter ("balanced" vs. "always shortest" vs. "always fast") to introducing protocols that abstract the diffing algorithm itself. The core team discussed these idea of parameterizing the diffing algorithm, but felt that it added complexity (to the implementation, to the API, etc.) for everyone without necessarily serving the needs of every user.

As an example, consider sort: we absolutely could parametrize sort based on various policy decisions (stable vs. unstable, whether it is allowed to allocation additional storage during its execution), and there are users for which the these choices may be critical. However, we have chosen not to expose such policies, opting instead for a simple API backed by an algorithm that works well for most people most of the time.

The presence of sort, or differences(from:), or any other algorithm in the standard library does not preclude the existence of a special-purpose package that does that one thing better. It would be great to have a Swift DiffUtils package that implements multiple algorithms and allows power users to tune their behavior. However, we don't need or want the full complexity of that in the standard library, where it's better to have a simpler API that works for many applications.


[Pitch] Remove duplicate elements from a collection
(Dave Abrahams) #42

That's not consistent with my recollection. IIRC we were forced to make them unidirectional because Foundation doesn't provide reverse enumeration for bridged NSSet and NSDictionary representations. I remember being really disappointed that we had to make that sacrifice; certainly there's nothing inherent about the Swift-native data structures that makes them unsuitable for bidirectional traversal.