Distinguish between ordered and unordered sets and maps (urgent; can only be implemented before beta releases)

[Laxystem]

trafficstars

The current implementation of sets and maps being 'ordered by default' is unintuitive as it isn't actually 'by default'; One would expect a persistent set to count as a persistent set, regardless of its order-ness.

val ordered = persistentSetOf("")
val unordered = persistentHashSetOf("")

check(ordered === ordered.toPersistentSet()) // true
check(ordered === ordered.toPersistentHashSet()) // false
check(unordered === unordered.toPersistentSet()) // false, what
check(unordered === unordered.toPersistentHashSet()) // true

Additionally, why do ordered sets even exist? Isn't the whole point of sets that they're unordered, unlike lists? Regardless, why are they default? Why are ordered maps the default too, for that matter? They're slower, and orderness isn't a part of maps' and sets' contracts; sure, it is a nice option sometimes, but then you could just explicitly use ordered variants; but for most use cases, wouldn't it make more sense to prioritize speed over a feature that isn't a part of the contract?

My solution

I'm assuming in both that the soon-to-be released beta will break backwards compatibility completely, as #185 talks mainly about public API changes. An educated guess tells me this is because this library is being merged into the stdlib, which means we can change the functionality of existing methods.

1. Rename the regular persistent builders to orderedPersistent (toOrderedPersistentSet, orderedPersistentMapOf(), etc.; or persistentOrdered, doesn't really matter).
2. Re-add the persistent builders (for both set and map; this is just an example), except for a tiny difference in implementation; Instead of:

   public fun <T> Iterable<T>.toPersistentSet(): PersistentSet<T> =
           this as? PersistentOrderedSet<T>
           ?: (this as? PersistentOrderedSetBuilder)?.build()
           ?: PersistentOrderedSet.emptyOf<T>() + this
   

   Have:

   public fun <T> Iterable<T>.toPersistentSet(): PersistentSet<T> =
           this as? PersistentSet<T> // changed here
           ?: (this as? PersistentSetBuilder)?.build()
           ?: PersistentOrderedSet.emptyOf<T>() + this // imo should be changed to hash but doesn't really matter
   

3. Keep the hash builders as-is.

TL;DR of the solution:

val ordered = persistentOrderedSetOf("")
val unordered = persistentHashSetOf("")

check(ordered === ordered.toPersistentOrderedSet()) // true
check(ordered === ordered.toPersistentHashSet()) // false
check(unordered === unordered.toPersistentOrderedSet()) // false, ok this time
check(unordered === unordered.toPersistentHashSet()) // true

// and also
check(ordered === ordered.toPersistentSet()) // true
check(unordered === unordered.toPersistentSet()) // true

As for "but what about other implementations?" --

1. #147
2. You could add PersistentOrdered and PersistentHash (or immutable versions of them) interfaces; but it's impossible this symmetric with mutable collections without hacking the type system even further, because of Java.

[JakeWharton]

Are you using === on purpose? Whether or not the "to" functions return the original instance or not is an implementation detail, not something that should be relied upon.

Additionally, why do ordered sets even exist? Isn't the whole point of sets that they're unordered, unlike lists?

Not really, no. The whole point is that things only appear once.

Order can still be an important characteristic for collections regardless of whether items can only appear once or not. Java just added explicitly-ordered sets under the name "sequenced" two versions ago, but of course it had sets which preserve order as implementation detail basically forever as well.

[Laxystem]

Are you using === on purpose? Whether or not the "to" functions return the original instance or not is an implementation detail, not something that should be relied upon.

Yes, it would've been is OrderedSet and is HashSet respectively, but Java prevents such interfaces from existing.

Not really, no. The whole point is that things only appear once.

Fair enough.

[qwwdfsad]

Indeed, whether toPersistentSet (or any other collection builder, adapter or transformer) returns the set of the same identity is often an implementation detail not to be relied upon, unless it is explicitly documented. Generally, it's not recommended to operate on collections identity, as they are a structural unit with a well-defined equality contract, with identity being just an implementation detail or a small optimization.

For such changes or proposals, usually the best thing to focus on is to start with the problems being solved and the desired effect (aka answering why the solution should be the way it is and what kind of an actual programmer's problem is being solved).

W.r.t the ordered thing -- it is consistent with the standard library, where the default behaviour of toSet and toMap is to preserve the insertion order, and an explicit opt-in is required to create a non-insertion-ordered container. In general, people depend on the default order in one way or another, and being insertion-ordered by default is a nice compromise (between the footprint and the overall usability) with a clear mechanism to opt-out

[Laxystem]

For such changes or proposals, usually the best thing to focus on is to start with the problems being solved and the desired effect (aka answering why the solution should be the way it is and what kind of an actual programmer's problem is being solved).

The problem here is that using toPersistentSet on an unordered set converts it into an ordered set, although the expected behaviour is for it to remain unordered, as it cannot be ordered.

[kyay10]

@Laxystem one may want to "preserve" the apparent ordering that the unordered set has, so that further insertions keep that same ordering. I agree that the naming is confusing at first glance, but once you're familiar with the library, it's clear that toPersistentSet would give you an ordered collection, just like persistentSetOf does. In other words, it's confusing from the outside, but it is internally consistent