[swift-collections 1.1] Heap API RFC

[lorentey (Karoy Lorentey)]

Great questions!

@wadetregaskis

I feel like I'm missing something, regarding all this and particularly what leads to the concluding sentence. It seems to be saying that instead of e.g. putting Strings in a Heap, it's expected that most uses will have some custom wrapper around String instead?

No — if you want a heap of Strings, and you’re happy with String’s ordering, then Heap<String> is perfect. All I’m saying is that it’s no big deal if you want your heap to use a different order.

If you need a custom ordering relation, then you’ll simply need to wrap your strings in some custom type of your own. (This is not a design defect, but it’s very much by design. Defining new types is easy.)

@wadetregaskis

This seems related to Swift's general choice to eschew collection-instance-specific customisation of equality / hashing / comparison. As opposed to e.g. C++ where STL (and Boost etc) collection types are typically parameterised (via the generics system) for these factors.

Yes, this is directly following a clear, strong pattern established by the Swift Standard Library. Set is a collection of Hashable elements, not a collection of arbitrary elements with a separate type parameter that describes how to compare and hash them.

As I noted in point (7), Swift does not make it possible to supply default values for generic type arguments, so trying to do C++-style mix-in parameters would make the API unpalatable for the common case.

@wadetregaskis

Even in Swift there are exceptions to this apparent rule, e.g. the standard sort et al methods take an optional comparison closure.

So hopefully this isn't too tangential or generic (vs Heap), but even knowing Swift's patterns it's not apparent to my why new collections should be implemented this way.

The crucial distinction is that sort et al. are generic functions, not generic types. A type whose values can get passed around in between modules of an app generally needs to guarantee a particular behavior for itself, so that code can usefully interact with it.

All code that encounters a Set<String> needs to agree on how == and hash(into:) get implemented.

All code that deals with SortedSet<String> values need to agree on how the ==/< relations work.

All code that receives a Heap<String> is guaranteed that the minimum and maximum items will be the ones that correspond to the < relation.

Swift is a strongly typed language. We like Swift's rich type system, and we want to make the best use of it.

This topic has been extensively covered in previous discussions, some of them directly involving Heap. (Beware, the linked discussion ended quite rudely.)

@wadetregaskis

Plenty of Collection- and Sequence-conforming types have undefined orders of iteration, e.g. Dictionary ("The order of key-value pairs in a dictionary is stable between mutations but is otherwise unpredictable.").

Set and Dictionary directly conforming to Sequence is an API design regret. If we were starting from scratch, I’d probably push for moving these conformances into a separate view, just like with Heap. (Suggesting such a move may have been possible in Swift 1 era. I don’t think it would be practical today.)

@wadetregaskis

It'd be one thing if unordered were an actual view that might have a different presentation to the base type, e.g. String's unicodeScalars, but it sounds like it's nothing more than the actual internal storage?

Like OrderedSet's elements view, Heap's unordered view simply directly exposes the underlying Array instance. This does not in any way lessen its view-ness -- it is still a bona fide, card carrying, actual view!

A view simply provides an alternate way of looking at the underlying representation, different from the default one.

The name unordered comes from OrderedSet's unordered view, where it is used to provide a SetAlgebra conformance. (As SetAlgebra's expectation for equality is incompatible with OrderedSet's order-sensitive equivalence relation.)

Heap's unordered view fulfills an analogue role for Sequence/Collection as OrderedSet's unordered view did for SetAlgebra.

(Note: TreeSet and TreeDictionary did not relegate their Sequence conformances to a separate view, as they are designed to be drop-in replacements of Set and Dictionary -- they needed to faithfully emulate their API surface, wrinkles and all.)

@wadetregaskis

That seems less flexible for the future, since it's explicitly stating that unordered is an Array<Element> - and therefore making it a potentially expensive operation if the underlying storage is one day made something else - whereas if Heap were simply a Collection itself it could abstract away any connection to the internal storage.

Min-max heaps are, by definition, represented by an implicit tree stored in an array. Having to expose this storage is not going to ever become a limitation.

(Note: We are not trying to pretend that it would be practical for Heap to switch to some radically different implementation, such as Fibonacci heaps. If we want to implement a different data structure, then we'd do it by defining a different type.)

If we ever want to generalize Heap to support storage types other than Array, then we will be able to do so by doing that in a separate type, as explained in point (7).

As has been very clearly noted, we sometimes want to form a heap in place using some pre-existing storage -- and this initial form of Heap intentionally does not allow that.

This is similar to how we decided that OrderedSet would hardwire Array as its underlying storage -- just like with Heap, it would sometimes be useful to be able to define, say, a uniquing Deque, and the current OrderedSet does not allow that.

(For what it's worth, in the three years OrderedSet has been in use, I have seen zero requests for generalizing it -- even though a Deque-based OrderedSet would allow allow efficient insertions/removals at its start, not just at its end.

That said, I think Heap is a bit more likely to receive such requests, so I expect we'll eventually end up doing this -- but probably not before we have non-copyable sequence/collection protocols. Most heap operations are implemented on the core Heap._UnsafeHandle type, which is an UnsafeBufferPointer-like construct, abstracting away the minutiae of Array access. One way to reformulate this in a safer way would be to use something like a non-copyable BufferView -- this would let us define a fixed-size, backing-store agnostic contiguous heap type as a public replacement of Heap._UnsafeHandle, and then use it in all sorts of generalizations of Heap.

I don't think any of these future directions need to hold up the release of Heap in the source-stable (but not ABI-stable!) swift-collections package.