PermutableCollection protocol

Evolution Pitches
22

Thank you for your thoughts @lorentey. I was remiss in not referencing our prior conversation that helped inspire this post.

I am somewhat surprised that the question of use-cases keeps coming up. Ultimately, it is impossible to argue for the necessity of PermutableCollection. I posit that it is similarly difficult to justify the need for RangeReplaceableCollection. We can always just use an Array for base storage and then choose the functionality that we need. Personally, I have more more use cases for a permutable protocol than a range replaceable one.

With that caveat aside, a strong argument can be made for situations where PermutableCollection would be uniquely helpful from a convenience and enforcement standpoint:

  1. any protocol/collection that wishes to provide in-place sorting without mutation
  2. any protocol/collection that wishes to provide in-place sorting while allowing selective mutation

Potential protocols that could inherit from PermutableCollection:

  1. an IndexReplaceableCollection: func replace(elementAt index: Index, with element: Element) -> Element?
  2. an IdentifiedCollection that enforces the uniqueness of each element's identity: `
  3. a KeyedCollection that enforces the uniqueness of a designated KeyPath of each element.
  4. a DocumentCollection that supports multiple keys that are included as part of the element
  5. a SwappableCollection (perhaps a typealias of PermutableCollection) to be used in cases where the sorting the underlying data object would be more efficient (or only possible) using swapping rather than replacement. i.e. if the indices where stored separately from the elements.

Concrete examples are of course endless, but let's try a few...

  1. Users a sortable collection of users with a unique identifier that does not allow duplicate phone numbers
  2. Words a sortable collection of words with definitions that allows homonyms but not duplicates
  3. Entities a sortable collection that wraps or mirrors an underlying document-based database where successful update operations are dependent on a matching key.
  4. IdentifiedSet a sortable collection designed to be used with SwiftUI. First-class support for Binding, List, and ForEach. Does not allow insertion of duplicate element IDs or mutation of existing element identities.
2 Likes
23

I see; presumably Users/Words/Entities/IdentifiedSet would be wrappers built on top of OrderedSet or OrderedDictionary, providing a higher level of abstraction. Those are a good class of use cases; although they are all sharing the same underlying data structure, they build new layers on top and that could justify the addition of a new protocol.

If I understand correctly, the primary use case of PermutableCollection would be in-place sorting. Is that a fair assessment?

This does make me stress the second point in my post above -- how exactly would Words.sort work? If it was a generic algorithm expressed in terms of swapAt, then it would likely be significantly slower in general than OrderedSet.sort. How big of an overhead are we prepared to accept?

Of course, PermutableCollection could include sort(by:) as a protocol requirement, and then Words etc could manually forward such calls down to the OrderedSet implementation. (This weakens the strength of the protocol a little, but it doesn't eliminate its value.)

But then again, wouldn't we want reverse() to be efficient, too? What about shuffle(by:)? rotateLeft(by:)/rotateRight(by:)? partition(by:)? Would we add all bulk reordering operations we could think of to the protocol, or would we just leave it at swapAt and sort, and leave the rest slow?

(I am intentionally ignoring your list of additional new protocols; understanding them or thinking through the consequences of them requires more careful thought than I am able to spend at the moment -- apologies! I might come back to them later.)

2 Likes
24

Yes, it would certainly be possible to build them with a base collection of OrderedDictionary and/or OrderedSet. It is also possible to build with an array and an unordered dictionary. It is also conceivable that we may be using a base collection (my Entities example) where we are not in control of the underlying storage. Of course the protocol does not mandate the base collection type.

Yes. More specifically in-place sorting where we can not allow carte blanche mutation.

I have created a working example in the link above. It includes an algorithm that converts re-ordered offsets to swaps. For example, a sequence of 3,2,1,0 would be equivalent to reverse(). Interestingly, that example requires only 2 swaps. If we were to sort with MutableCollection, it would require 4 mutations (with intermediate duplicates). I suspect there are situations where swapping is preferrable to mutating and vice-versa... perhaps depending on the type of the underlying store and what we are optimizing for.

There likely exists an optimized sorting algorithm expressed as swaps, though I would not know where to begin looking for it. I am not sure how it would compare to Swift's current sorting algorithm. Having an optimized algorithim (even if it is not perfectly efficient) included within PermutableCollection would be potentially advantageous.

@lorentey thank you again for another thoughtful conversation.

1 Like