Heap in its current iteration is not a Sequence. I don't think we need to change this.
In the (hopefully!) rare cases where a Heap needs to be passed to a function that takes a Sequence, Collection, BidirectionalCollection, or RandomAccessCollection, we can use the unordered view to treat it as one. The name of the view explicitly documents that the order of items is unspecified.
Do you think this isn't enough?
I think it is extremely detrimental to usability to ignore a protocol conformance that you meet the requirements for.
A sequence is a list of values that you can step through one at a time.
If you can do that with a min-max heap, and you obviously can, it should conform to Sequence.
If you donāt, people are going to pass unordered to everything reflexively, and then Array.min gets used for no good reason.
And I think it would be detrimental to Heap's usability if we'd pollute its member namespace with Sequence algorithms that implicitly make use of the unspecified ordering. ĀÆ\_(ć)_/ĀÆ
unordered is a nice compromise that lets people write for-in loops over heaps and call Sequence/Collection algorithms while also fixing a major gotcha. It gives you what you want, while also giving me the piece of mind that the ordering is never relied on without an explicit callout in the code highlighting that it's unspecified.
The fact that a type can conform to a protocol doesn't necessarily mean that it's a good idea to actually add the conformance. For example, Heap could technically also conform to Equatable and Hashable -- but I find it would be a bad idea for it to do so, for similar reasons as with Sequence. (Note that Heap.unordered is Hashable when Element is.) The same goes for Codable -- I wouldn't trust deserialized contents to be heapified, so it's better to just serialize/deserialize the unordered view.)
I feel it is rather important to follow precedents set by the standard library, and Set provides a fairly clear precedent here. Set is a Collection because order is consistent unless mutated. Even if that isnāt true for a heap, the rationale for being a Sequence holds.
As for being Codable: a Set canāt necessarily trust elements to be unique, but that doesnāt prevent conformance.
Apologies for using an Appealing to Authority argument here, but I feel it's legitimate in this case.
I wrote the current iteration of Set and Dictionary, and I've seen & responded to a few years' worth of bug reports relating to their unordered nature. I do not think they make good precedent for API design. (Although my primary beef is with their Collection conformances, not necessarily Sequence.)
More importantly, as I mentioned above, unlike Set/Dictionary, I do not think that Heap is first and foremost a container type. I can only think of a few use cases for iterating over a Heap, and they all feel inadvisable to me.
Do you have motivating use case for treating a Heap as a Sequence?
Iterating through it.
Why would you want to iterate through it?
OK, fine. If you arenāt planning to expose any behavior akin to Sequence, conformance isnāt necessary.
As for Collection conformance on Set and Dictionary, the indices are consistent until mutation occurs. No Collection has indices that are guaranteed to point to the same thing after mutation. Not even Array. So thatās normal.
Glad we're on the same page now.
Well, the initial post was prompted by the ascending/descending properties, which is Sequence behavior. Is there anything else related to iteration?
If you donāt want to treat it as a Sequence itself, I say you should also scrap every declaration that is simply calling the array that backs it. isEmpty, count, etc. Those arenāt even required by Sequence: theyāre from Collection.
Please note that in the quoted post, I'm not arguing that ascending/descending need to be removed because they're Sequences.
Heap.isEmpty and Heap.count are indeed related to the similar Collection requirements, but you're misrepresenting my position. I don't have some weird, mindless agenda against implementing operations that also happen to be provided by Collection.
These two properties (1) are usually considered core operations of the binary heap ADT, and (2) they aren't exposing (& aren't affected by) the ordering of elements within the heap.
I thought your position was that it isnāt a container, just holding one. How could that be empty or not empty?
By the way, thank you for being patient with my suggestions.
My position is that iterating over all the elements is not normally a thing one needs to do in a binary heap -- in fact, I think I'm okay to stick my neck out and say that code that needs to do this ought not to use a heap at all. For example, if the goal is to implement a unique heap, then calling Heap.contains before insertions would be a horrible way to avoid duplicates.
Wikipedia is a terrible resource for learning about data structures, but not even it lists iteration as a heap operation.
Itād be great if there was a database of data structures that you could search according to characteristics (of memory usage, performance, guarantees, etc.). Iām sure thereās a lot of obscure and seldom-used constructs that Iād take advantage of if I only knew about them.
I read the paper cited in the documentation for Heap before making this post, myself. I didnāt want to waste anyoneās time by misunderstanding the subject matter.
I wonder if we could consider another name for this view.
Thereās nothing about āunorderedā that clearly indicates itās a sequence, or any sort of view for that matter; and it in fact exposes an order (iteration order)āit's the base heap that's unordered, not the view, and indeed that's the whole point.
Perhaps: arbitrarilyOrdered, or just elements?
You're not appealing to authority (i.e., claiming an assertion as true because of the status of someone who stated the assertion); you're sharing your experience as an authority on the topic, which is vital!
elements seems perfect to me.
As an aside, could you provide any detail here around which aspects users find confusing? In my experience with more junior developers, almost all grasp that Set and Dictionary don't respect insertion order once that's been stated (few intuitively understand what unordered means here). What they do find confusing, however, is the fact that the order is affected by insertion order, subsequencing, and can change between runs (this also bleeds into the type's usability at all). I'm curious to know which aspect finds its way through reports the most.
+1 - definitely so, there are most likely way better alternative data structures to use then - would be happy to hear of any real-world use case to prove otherwise.
Also +1 for "elements", it would be more discoverable I think.