I reached for oset because I wanted a sort+dedup of some slices, and oset looked comparable to python's set()
. This bit me, because oset specifically does not define equivalent elements as indistinguishable. That is, I incorrectly assumed the following:
var a, b SomeFancyType = mkFancy(), mkFancy()
// The values are distinct in some way, but their comparison function deems them equivalent.
Assert(a.Compare(b) == 0)
os := oset.NewFunc(SomeFancyType.Compare, a, b)
Assert(os.Len() == 1) // Oops, boom, os.Len() == 2
I'm not sure if this is a bug or not. oset does not say that it deduplicates anything. However, I think that also makes the type not a set, by the strict mathematical definition? You can add 3
to an oset twice, and get both back out when iterating. That makes it... something else, possibly a non-decreasing subsequence, which could probably be abbreviated to oseq
.
I'm not sure what to do about this. I started writing a PR to document this behavior, but then started wondering if this going against the assumptions Go programmers have about sets and equivalent elements is intentional, whether it should be changed vs. merely spelled out more explicitly, and then a whole existential crisis about whether it's even a set at all if it allows duplicate members. So, opening this issue to spread the love, I suppose ๐
Options I can think of:
- Document that oset departs from the de-facto expectation of how sets behave in Go, and that it is strictly speaking not a set
- Rename package to something else, e.g.
oseq
, to more precisely capture its "sorted list with more efficient insert than slices"-ish behavior.
- Change oset to store only distinct elements, with
Compare(a, b) != 0
being the definition of distinct.
Genuinely unsure which to pick, I think I ever so slightly lean to changing the semantics to be a proper set, possibly alongside making a separate package for the ordered sequence semantics? WDYT?