But there are two values or instances in play, not one. Which one goes to the end — the one that's already in the set, or the one you've asked to be added?
I agree with @karim's solution, where you say what you mean unambiguously, without new API.
1 Like
Maybe we should start by describing what protocols an OrderedSet conforms to? RangeReplaceableCollection?, etc?
1 Like
I'm definitively not an expert on Swift's collections protocols, but just to get the ball rolling, here's my first pass at what an OrderedSet's conformances might look like:
RandomAccessCollection
CustomDebugStringConvertible
CustomReflectable
CustomStringConvertible
CVarArg
Decodable
Encodable
Equatable
ExpressibleByArrayLiteral
SetAlgebra
Hashable
After reading through the various collection protocols, it seems to me that RandomAccessCollection conformance is the best starting point for the base collection behavior.
The ones that are stumping me are:
MutableCollection: This seems like a desirable interface (sorting, reversing, swapping, etc), except that mutability via subscript creates weird edges around the uniqueness constraint:
var orderedSet: OrderedSet = [1, 2, 3]
orderedSet[0] = 3 // <-- What should happen here???
Likewise, RangeReplaceableCollection introduces some nice interface (insert, append, remove, etc), but I'm not sure how to reconcile the protocol-defined interfaces (init(repeating:count:) 
) with the set-like behavior.
Do we just mimic some of those protocols' interfaces in a more limited and non-protocol-backed way? Do we attempt to restructure these two protocols into smaller, more atomic properties?
Thoughts?
Well, based upon the MutableCollection documentation (relevant excerpt below), as a uniquing collection it should remove all instances of the value 3, then, as a MutableCollection it should replace the element at index 0 with the value 3.
Note the order, because after the entire subscript, the new value 3 must be at the specified index for it to be a valid MutableCollection.
MutableCollection documentation excerpt:
/// A value stored into a subscript of a
MutableCollectioninstance must
/// subsequently be accessible at that same position. That is, for a mutable
/// collection instancea, indexi, and valuex, the two sets of
/// assignments in the following code sample must be equivalent:
///
/// a[i] = x
/// let y = a[i]
///
/// // Must be equivalent to:
/// a[i] = x
/// let y = x
1 Like
That's not how NSMutableOrderedSet works today though:
let set = NSMutableOrderedSet(array: [1,2,3])
set[0] = 3
print(set) // [1,2,3]
If the inserted element is not retrievable at the index one sets it to, the type should not conform to the MutableCollection protocol. If it declares conformance regardless, it is a bug. (see MutableCollection documentation excerpt above)
2 Likes
Right, so it seems like we wind up creating API which seems on the surface like MutableCollection, but doesn't actually behave that way, which is... ugly 
So here's a good example to form some decisions around.
// NSMutableOrderedSet: "If the object is already a member, this method has no effect."
set.insert(3, at: 0)
// RangeReplaceableCollection: "The new element is inserted before the element currently at the specified index"
set.insert(3, at: 0)
How important is it to hew to the NSMutableOrderedSet semantics? I can see a few approaches in this case:
- Conform to
RangeReplaceableCollectionand cut ties with strict adherence toNSMutableOrderedSetbehavior - Maintain
NSMutableOrderedSetbehavior at the cost ofRangeReplaceableCollectionconformance- Optionally, spell the interface very differently from
RangeReplaceableCollectionto avoid confusion... Except thatinsert(_:at:)is really the right name for this operation.
- Optionally, spell the interface very differently from
- Do something entirely different that I haven't thought of yet
Note that MutableCollection and RangeReplaceableCollection are not the same thing.
For example: String is a RangeReplaceableCollection, but not a MutableCollection, because character combing could cause the inserted character to not be in the String.
However, a FixedLengthArray (if we get one of those) would be a MutableCollection, but not a RangeReplaceableCollection because one could replace an element, but not insert an element, because that would change its length.
But, if semantic constraints could be resolved, an OrderedSet could be both a RangeReplaceableCollection and a MutableCollection
Right. My initial conflation of the two in that post (pre-edit) was an error born of changing my thought-process mid-post.
In either case tho, the problem comes down to the same thing: adhere tightly to the NSMutableOrderedSet behavior, or break it in favor of Swift protocols conformance.. it’s a fundamental direction we’ll have to decide on to move forward.
1 Like
I think we should make this type follow the rules and precedents set (ha ha) by the collection protocols in the standard library. If we need to design a new protocol, that may also be in scope.
Now - I don't mean to abandon ship on it feeling like NSOrderedSet, but if there is a fundamental mismatch I think we should err on the side of behaving like the rest of the platform.
Case in point: Data slicing follows the same rules about how indexes work as Array does. NSData's subData instead returns something indexed starting at zero. This is a point of confusion, but in the end we decided it was better to follow the precedent in the stdlib.
5 Likes
This is great input. Given this, it really does become a question of looking at each requirement of RangeReplaceableCollection and MutableCollection (which at least on the surface both make sense to me to try to conform to), and see if A. we can reasonably conform to them, B. we want to conform to them, and C. are there any other interfaces this type should have that don't fit in to these.
Does that seem like a reasonable approach?
That sounds like a great place to start to me.
How do we envision people using this new type with CoreData? NSOrderedSet is heavily used there and it would seem that this new OrderedSet would fill a similar role for Swift CoreData users. Are there any considerations we need to make to the design to make sure this works well?
FWIW, Set doesn't conform to MutableCollection, and I think there's an argument that OrderedSet ought to have the semantics of Set as far as possible, so that rules out MutableCollection conformance. I'm not sure about RangeReplaceableCollection offhand.
Regarding things like:
orderedSet.insert(3, at: 0)
my initial impression is that letting such things reorder the set via side-effects is going to be a usability nightmare. I think it's better to take the simpler path, where there's a general rule that objects presented for insertion (whether singly or part of an argument that's itself a collection) should be silently ignored.
This happens to be the NSMutableOrderedSet behavior. I don't think OrderedSet should use that behavior because NSMutableOrderedSet does, but because it seems like a superior choice.
Adopting this behavior doesn't mean we can't have API to reorder the set, but it doesn't seem to me to be a good idea for that API to insert anything at the same time.
Lastly, I'll remind everyone again that when an insertion of an "equal" element is considered, there are (up to) two different values or instances to consider: one already in the set, and one presented for insertion.
That's another reason why I don't like the re-organizing behavior of an insert. It'd be odd to discard the inserted instance, but move the different-but-equal instance inside the set to a different place in the set.
In general, I'd say, it's a bad idea to use sets of Ints for quick examples. Better to use an Equatable type where == isn't trivial.
@QuinceyMorris, you're raising (again) really good points, especially the one about "equal but different" items being inserted. Thanks. We really need to not forget that reality.
At the same time, I can think of several really good use-cases for an insert(_:at:) or analogous API. Is there something we can do better than silently ignoring duplicates?
Is it worth considering something like this?
func insert(_ element: Element, at index: Index) throws
Where instead of silently ignoring the insert, we explicitly reject the operation?
Thinking on this, OrderedSet could have an additional version of insert that returns the value, if any, that was in the collection but removed due to the uniqueness restriction, and perhaps the index it could be returned to, which may be different from the index it came from.
If one wants to preserve the old value, it would then be simple to do so:
guard let old = insert(new, at: index) else { ... }
if shouldPreserve(old) {
_ = insert(old, at: index) // or whatever else.
}
A more conventional insert would be required for RangeReplaceableCollection conformance, that returns Void, and care would have to be taken to ensure they could be easily disambiguated, but it could be possible.
But Set doesn't conform to MutableCollection in part (and perhaps indirectly) because it is unordered, so subscript-based mutation doesn't really make any sense for it. Presumably an OrderedSet has a stable ordering, and subscript-mutation and/or insert-at semantics have much more usability.
I'd suggest considering this from the point of view of a possible "insert(contentsOf:,at:)", taking a collection as the first parameter, and whether there is an understandable outcome if replacements/reorderings occur.
I think this is undesirable from the "set" side of the behavior. One of the really nice (and important) characteristics of a Set is that adding elements already in the set does nothing to the set, and has no performance or reorganization consequences. That is, there are many use cases where you blindly attempt to add, and don't care whether it adds or not, and that's the point of a Set.
I've got a feeling that something similar will still be import for OrderedSet. But I admit I haven't really spent a lot of time thinking this through.
FWIW, my recollection is that NSOrderedSet owes its justification for existence to Core Data primarily, and that in the Cocoa world, it is fairly widely reviled as not very performant. Both factoids probably ought to be considered in any new design. 