21

That’s not true. If you iterate through a Set, Dictionary, or Heap, and there’s been no mutation, you’ll always iterate in the same order. So long as value semantics are used, that cannot possibly be false.

There are no “hidden” protocol requirements. If a protocol doesn’t say it requires something, it does not require it.

22

In hindsight, I strongly believe adding the ascending and descending properties was a mistake. These properties do not work like views do in the Standard Library, and their performance characteristics are very surprising.

Luckily, Heap isn't part of a public Collections release yet, so it's still time to correct this. I filed PR #119 to remove these from the Heap implementation.

(People who find these properties helpful are of course welcome to define them in ad-hoc extensions, outside of this package. After all, these properties are merely lightweight wrappers over the public popMin and popMax APIs -- they are built entirely out of public API.)

Note that the unordered property does work like a proper view -- it exposes the contents of the heap as a RandomAccessCollection with integer indices.

The idea is that having to explicitly add .unordered to use a heap as a sequence/collection will highlight the fact that this container does not define a specific ordering for its elements.

1 Like
23

Sequence doesn’t imply a specific ordering, does it? It doesn’t even guarantee the elements exist after being accessed!

24

By painful experience, it seems that directly conforming Set to Sequence (much less Collection) was probably a mistake -- people do expect that these container types will provide a specific ordering.

And Set only constrains its Element to Hashable! I worry that constraining Element to Comparable will make the ordering assumption even more prevalent for Heap.

In addition, I do not think that iterating over contents is a hugely important heap operation. What's a good motivating use case for it?

1 Like
25

I don't think it's the specific order that confuses people as much as the randomly changing order that started after randomized hashing was introduced. That, and the subtleties around order of insertion can be very confusing. Those aren't really the fault of protocol conformances, just the subtleties of implementation that perhaps aren't visible enough.

4 Likes
26

Any generic algorithm that accepts a Sequence? The many Sequence methods you are otherwise reimplementing with different semantics? There’s plenty to choose from.

Consider, for instance, Sequence.sorted, Sequence.min(_:), Sequence.max(_:)…

27

Personally, I think that anyone who ignored documentation explicitly saying things were unordered has no one to blame but themselves.

28

These algorithms are all available -- they are just spelled, e.g. heap.unordered.sorted().

One good reason to push the Sequence conformance down to a view is to remove the multitude of irrelevant Sequence algorithms from the primary heap namespace. Nobody should ever call Sequence.min() and max() on a Heap.

29

Why not? You can have O(1) implementations of them, no?

30

Not in contexts generic over Sequence, no.

31

That's not really a useful way to look at it. Relatively few developers are familiar with "unordered" in this context, especially when the values obviously do have an order since you can iterate them consistently. Anything less and the types would be rather useless. And to be clear, Set's documentation calls out the "unordered" nature of it only once, "An unordered collection of unique elements.", and doesn't mention anything in the iteration section or elsewhere. So it can hardly be surprising that users miss some aspect of the type's behavior here.

1 Like
32

Sequence explicitly doesn’t imply consistent iteration.

33

And the time complexity of Collection.count is O(n), not O(1), even if it is backed by a RandomAccessCollection. I feel that is an extremely bad reason to avoid conformance.

34

I was talking about Set here, but Sequence is very surprising to most people that way, especially when there are so few examples to be aware of that actually exhibit that behavior.

35

There is a reason most of the Sequence methods that involve order return arrays.

36

Not in contexts generic over Sequence, no.

To expand on this a bit, if Heap conformed to Sequence, then this code will not use the O(1) implementations:

func foo<S: Sequence>(_ items: S) -> S.Element? where S.Element: Comparable {
  items.max()
}

let heap = Heap(0 ..< 100)
print(foo(heap))

This alone wouldn't be a good argument not to conform Heap to Sequence -- after all, SortedSet will definitely be a Sequence, even though it will have the same behavior.

The difference, as I see it, is that Heap doesn't feel like a container the way SortedSet feels like a container. Yes, it contains elements, like SortedSet does, but it feels to me that the primary way to retrieve its contents is through max()/removeMin/popMax etc, not by direct access.

(I know it's infuriating to argue on API design based on about how things feel. Sorry.)

37

This isn't a true statement -- RandomAccessCollection.count is an O(1) operation.

1 Like
38

Collection has an O(n) default implementation for count. I fail to understand how that is any different from concerns about Sequence.min being given an O(1) implementation for Heap.

39

That’s the thing: a Sequence is not a container. It’s an iterator with delusions of glory. Sequence conformance doesn’t say anything about containing elements.

40

This is a consequence of the fact that distance(from:to) is O(1); RandomAccessCollection explicitly calls this out in its docs.