proposal: container/set: new package to provide a generic set type (discussion)

[ianlancetaylor]

This is a discussion that is intended to turn into a proposal.

This proposal is for use with #43651. We propose defining a new package, container/set, that will introduce a new set type. It is possible that this proposal, if accepted, will be included with the first release of Go that implements #43651 (we currently expect that that will be Go 1.18). Or it may be appropriate to delay this package until a later release. This package will not be in the 1.18 release, but is for consideration for a later release.

This description below is focused on the API, not the implementation. In general the implementation will be straightforward.

See also the slices proposal at #45955 (discussion at #47203) and the maps proposal discussion at #47330.

// Package set defines a Set type that holds a set of elements.
package set

// A Set is a set of elements of some comparable type.
// Sets are implemented using maps, and have similar performance characteristics.
// Like maps, Sets are reference types.
// That is, for Sets s1 = s2 will leave s1 and s2 pointing to the same set of elements:
// changes to s1 will be reflected in s2 and vice-versa.
// Unlike maps, the zero value of a Set is usable; there is no equivalent to make.
// As with maps, concurrent calls to functions and methods that read values are fine;
// concurrent calls to functions and methods that write values are racy.
type Set[Elem comparable] struct {
	// contains filtered or unexported fields
}

// Of returns a new set containing the listed elements.
func Of[Elem comparable](v ...Elem) Set[Elem]

// Add adds elements to a set.
func (s *Set[Elem]) Add(v ...Elem)

// AddSet adds the elements of set s2 to s.
func (s *Set[Elem]) AddSet(s2 Set[Elem])

// Remove removes elements from a set.
// Elements that are not present are ignored.
func (s *Set[Elem]) Remove(v ...Elem)

// RemoveSet removes the elements of set s2 from s.
// Elements present in s2 but not s are ignored.
func (s *Set[Elem]) RemoveSet(s2 Set[Elem])

// Contains reports whether v is in the set.
func (s *Set[Elem]) Contains(v Elem) bool

// ContainsAny reports whether any of the elements in s2 are in s.
func (s *Set[Elem]) ContainsAny(s2 Set[Elem]) bool

// ContainsAll reports whether all of the elements in s2 are in s.
func (s *Set[Elem]) ContainsAll(s2 Set[Elem]) bool

// Values returns the elements in the set s as a slice.
// The values will be in an indeterminate order.
func (s *Set[Elem]) Values() []Elem

// Equal reports whether s and s2 contain the same elements.
func (s *Set[Elem]) Equal(s2 Set[Elem]) bool

// Clear removes all elements from s, leaving it empty.
func (s *Set[Elem]) Clear()

// Clone returns a copy of s.
// The elements are copied using assignment,
// so this is a shallow clone.
func (s *Set[Elem]) Clone() Set[Elem]

// Filter deletes any elements from s for which keep returns false.
func (s *Set[Elem]) Filter(keep func(Elem) bool)

// Len returns the number of elements in s.
func (s *Set[Elem]) Len() int

// Do calls f on every element in the set s,
// stopping if f returns false.
// f should not change s.
// f will be called on values in an indeterminate order.
func (s *Set[Elem]) Do(f func(Elem) bool)

// Union constructs a new set containing the union of s1 and s2.
func Union[Elem comparable](s1, s2 Set[Elem]) Set[Elem]

// Intersection constructs a new set containing the intersection of s1 and s2.
func Intersection[Elem comparable](s1, s2 Set[Elem]) Set[Elem]

// Difference constructs a new set containing the elements of s1 that
// are not present in s2.
func Difference[Elem comparable](s1, s2 Set[Elem]) Set[Elem]

[randall77]

Needs some sort of performance promise. I think it would be ok to promise that Add and Has are amortized O(log(n)).
Not sure we need to enumerate that everywhere, but maybe a note at the bottom of package docs would list promises for all the functions.

[robaho]

The implementation of a map won’t change so neither will it’s performance. There is no such thing as the “performance of a set” - it’s the performance of the implementation - which can vary based on the operation (get, remove, iterate, etc) and other characteristics (memory vs cpu, etc)

e.g a TreeSet has different performance characteristics than a HashSet - similarly for a set backed by a map.

[apparentlymart]

I'm not sure if you were replying to me specifically @robaho but in the interests of being clear: my comment was assuming that we are talking about a specific implementation of sets rather than the general idea of sets, because the original message showed a struct type and subsequent discussion has been explicit that this is talking about only a thin wrapper around a map for the initial implementation. My question was therefore about whether the participants in this sub-thread would be satisfied by a promise of performance relative to the built-in map implementation, rather than a promise of a specific big-O complexity.

You're right that it doesn't make sense to make performance promises about an interface, and so if I misunderstood and this is instead talking about an interface intended to be implemented elsewhere (outside of the standard library?) then indeed my question (and possibly this entire sub-thread) is moot.

[robaho]

I am not sure you can discuss a specific implementation of a set then go create an interface that has different method signatures - so you are defacto defining the interface by creating the implementation first (unless creating wrapper structs is on the table - which seems not ideal for core stdlib collection implementations).

[Merovius]

@apparentlymart

my comment was assuming that we are talking about a specific implementation of sets rather than the general idea of sets, because the original message showed a struct type and subsequent discussion has been explicit that this is talking about only a thin wrapper around a map for the initial implementation.

You assumed correctly.

My question was therefore about whether the participants in this sub-thread would be satisfied by a promise of performance relative to the built-in map implementation, rather than a promise of a specific big-O complexity.

Personally, I could accept this, but it seems very awkward to me. There aren't really "equivalent map operations" per se. Like, yes, we will know what it means, but it kind of breaks the entire idea of not talking about the implementation and hiding it in a struct, if we say "just pretend that it's a map[T]struct{} and s.Add(v) is the same as s[v] = struct{}{}" or whatever.

So, just writing down actual complexity classes seems easier and less ambiguous. And I don't see a lot of downsides either. We do it for container/heap, for example. It's a very important and useful piece of information about a data structure, so why not just provide it?

[apparentlymart]

I suppose I was imagining this being a brief sentence in each operation's documentation stating which map operation the set operation is analogous to. For example, for Add: "Worst-case complexity is guaranteed equivalent to insertion of a new element into a map."

With that said, I also don't have any objection to stating that effect more directly. For some reason on my initial read of this discussion I understood that there was some concern about doing that and so I was attempting to propose a compromise. However, on re-read I can see that I misunderstood and the question was instead whether this should be a concrete implementation at all, vs. an interface with potentially many implementations that would each have their own performance characteristics. I'm sorry for the noise and I withdraw the suggestion.

[smasher164]

Regarding the naming, it seems inconsistent to me to have standalone functions named Union, Intersection, and Difference, when the set type has methods named AddSet and RemoveSet. It almost suggests that AddSet and RemoveSet perform a different operation (I understand they work in place).

[nickkeets]

FWIW Swift calls the in-place versions formUnion and formIntersection.

[ianlancetaylor]

I don't think it's inconsistent. The Union function forms a union of two sets. The AddSet function adds one set to another. While clearly the concepts are very similar I think it would be more confusing to have a Union function that returns a new set and a Union method that changes an existing set.

[ajlive]

I agree the function and the method should have different names, but I think Swift is at least on the right track here.

Scanning the API proposal above, I did a double-take at AddSet and had to check the comment to make sure I knew what it did.

FormUnion or, say, UnionWith, I think are more clear about both what the method does and what makes it different from the Union function.

[deanveloper]

I agree with Ian here - AddSet is a good name for a mutable function. Union (or anything containing the word) makes me think of immutable mathematical operations. FormUnion is okay I guess, but IMO it still could be mistaken for s1.FormUnion(s2) creating a new map. s1.AddSet(s2) is very clear that it adds s2 to s1.

[Merovius]

// (Note: New and Of are separate because New will always require a type parameter
// whereas Of will often be able to infer the type parameter from the arguments.
// For example, set.New[int] or set.Of(1, 2), but not set.Of[int]().)

I don't understand this argument (also, set.New[int]()). As Of is the more general function, this comment would suggest that New saves us having to write type-parameters - but it, of course, doesn't. "Always having to write a type-parameter" is clearly not a beneficial property of a function.

IMO there should just be one function New[Elem comparable](v ...Elem) Set[Elem]. It still allows you to write the same New call as before and you can get type-inference if you list the elements. Seems strictly better to me.

[Merovius]

In other words: AIUI Of[T]() will be equivalent to New[T]() so New is redundant and should be removed. Freeing up the canonical New name for Of.

[ianlancetaylor]

I wrote both because they read differently. But, yes, we could remove New.

[DeedleFake]

While New() seems more idiomatic, Of() actually reads quite well for both:

set.Of(1, 2, 3)
set.Of[int]()

[ianlancetaylor]

I've removed New to provide just Of.

I've also changed to pointer receivers, so that the zero value is useful.

[Merovius]

I find it awkward to say "Like maps, Sets are reference types" and having to explain that, instead of just making it a pointer. It might feel weird to always have to pass around a Set via a pointer, but for declared types, that's not super uncommon. And if we made every method use a pointer, we can make the zero value of Set equivalent to an empty set - maps are one of the main reasons why I often have to write constructors instead of have my zero values be useful, so I would prefer to be have useful zero values.

[bcmills]

Agreed — having to make all of the fields of map types within a struct gets pretty tedious. The meaningful zero-value is one of the few things about sync.Map that is more ergonomic than a built-in map.

[ianlancetaylor]

I've made the zero value useful by changing the methods to take pointer receivers.

[cespare]

I've made the zero value useful by changing the methods to take pointer receivers.

That seems like an improvement, but I think we should further encourage sets to be passed by pointer by having all functions that accept or return sets use *Set[Elem] rather than Set[Elem]. (So change Of, Clone, HasAny, Union, etc.) As it is right now, this type uses a mix of pointer and non-pointer types that looks pretty unusual for a data structure type.

[jhenstridge]

In particular, it means that none of the defined methods are in the method set of the value returned by Of(). While in many cases this doesn't matter, I suspect it will lead to confusion when people try to stuff sets into interface variables. Take the following contrived example, which would fail to compile:

type HasLen interface {
    Len() int
}
var foo HasLen = set.Of(1, 2, 3, 4, 5)

[fzipp]

Any reason why Union, Intersection and Difference are functions instead of methods? image.Rectangle has Union, Intersect and other binary operations as methods, image.Point and the types in math/big as well.

Methods would feel more like infix notation. My suggestion would be Set[Elem].Union, Set[Elem].Intersect, Set[Elem].Diff

[Merovius]

Any reason why Union, Intersection and Difference are functions instead of methods?

Union is AddSet and Difference is RemoveSet, except that they operate in-place. There's definitely value in having both an in-place version and a not-in-place version, so adding Union as a method would mean it's the not-in-place version. Personally, I find it unsavory to return a new Set from a method (Clone is an obvious exception). image.Rectangle is different, to me, because it has a constant (small) size.

[rogpeppe]

Why the requirement not to modify the set during iteration? Maps don't have that requirement and that's a very helpful property. Also, iterating by using a function is awkward (you can't just return from the outer function, or break more than one level of loop), so I wonder if it might be nicer to support some kind of iterator so iteration can be done with a straightforward for loop.

[Merovius]

Another huge difficulty, of course, is that when iterating []T, you might want to get the index you're at, for something like map[K]V you might want to get the key you're at and for something like chan T there is neither. So, a "general purpose iteration API" also needs to concern itself with how to resolve that.

FWIW we can always add methods to work with iterators, once we have an iterator interface.

[fzipp]

@Merovius I see the challenges, but in my opinion it is worth directing more energy towards figuring out an iteration concept before adding packages for collection types, i.e. lay the foundation before building castles. I see an iteration interface on the same level of fundamentality as io.Reader/Writer that turned out to be incredibly beneficial to the standard library.

[Merovius]

Note that io.Reader/Writer came after their concrete implementations, though.

[fzipp]

Note that io.Reader/Writer came after their concrete implementations, though.

@Merovius In 2008, before the public release (called io.Read and io.Write back then) 😁, long before a compatibility promise was in sight, and it actually seems like they were defined at the same time as the first concrete Read(er) implementations.

I don't find "we can always add it later" compelling in this case. It concerns 9 out of the 18 proposed functions/methods (50%). Adding the more general functions later will increase the API surface unnecessarily, and the good function names will be taken by the obsolete functions.

[ianlancetaylor]

It is not clear to me that we will want methods on Set that use iterators. Maybe we will, maybe we won't. In Go it seems to me more likely that iterator operations will take the form of functions. Containers will most likely need methods that provide an iteration mechanism, and then we might have a function like func AddTo(container.Addable, container.Iterator). (This may be a good argument that Set.Add should take a single element rather than a variadic, I'm not sure.)

Separately I'll note that Go already has a builtin iteration mechanism in the for/range statement. A general iterator mechanism should work cleanly with that, which will require language changes one way or another.

[fzipp]

"Len" is an unusual name for the cardinality of a set, the colloquial term is usually "Size". Of course, "Len" would fit the Len method in sort.Interface (but the proposed Set type can't be sorted), and other types are measured via the "len" builtin function, so that's probably where it comes from.

[DeedleFake]

Both bytes.Buffer and strings.Builder have a Len() method and aren't sortable, though they are ordered. While I agree that Len() isn't the usual name for the cardinality, I think that I prefer the consistency over whatever's going on with Java's standard library.

[ianlancetaylor]

I think Len is the standard Go name here. Even len(m) works for any map m.

[Cyberax]

Can we get explicit promises for the iteration order? And maybe another hashset without such promises?

[Cyberax]

Yeah, I don't necessarily want to impose order on all sets, just make it very explicit what kind of the collection you're dealing with.

[leighmcculloch]

A set that preserves not just order from one iteration to the next but insert order would be very useful.

[ianlancetaylor]

This type does not provide any ordering guarantee. This is intentional. I expect that over time there will be other set types that provide different performance/ordering guarantees.

[fzipp]

I expect that over time there will be other set types that provide different performance/ordering guarantees.

Interoperability between different set types will be difficult, because these methods and functions take concrete types: AddSet, RemoveSet, HasAny, HasAll, Equal, Union, Intersection, Difference

[ianlancetaylor]

I don't yet see a reason for an AddSet method that takes a generalized set. That's a role for a function that takes a container.Addable and a container.Iterator.

[cespare]

Making Add and Remove variadic doesn't feel quite right to me. These are two of the fundamental primitives for sets and having those methods involve slices seems like extra amount of complexity that doesn't sit flush with the rest of the API. I suspect that the vast majority of Add and Remove calls will have exactly one argument anyway, and there is some small performance penalty to the variadic version.

[cespare]

Personally, from an API perspective, I very much like that Add and Remove are variadic. It easily allows both to add a single element and a slice - and I don't even think adding a slice is that uncommon.

IMO the main reason to use a variadic function is if it will mostly be called with a variable number of arguments in the call. Sometimes in code review I see that someone has written a variadic function but then all the call sites look like f(s...). In that case, it would be better for the function to take a normal, non-variadic slice.

Here, my intuition is that the usage will look like this:

s.Add(v)            // very common
s.Add(vs...)        // an order of magnitude less common
s.Add(v0, v1, v2)   // another order of magnitude less

If that is roughly correct, then the purpose of this being variadic is a kind of backdoor function overloading to allow accepting both a single value and a slice, and mostly not to support s.Add(v0, v1, v2). That's what doesn't feel quite right to me. When I look through all the variadic functions in the standard library (there aren't many) I can't spot any that that seem like they are used this way. Most of them exist to support printf-like functionality.

If we want to support passing in a single value and also passing in a slice, I think that two separate functions (Add(Elem) and AddAll([]Elem)) are better.

I would personally expect them to be inlineable and thus have no penalty.

That does not follow. There is more work to be done to handle a slice than there is to handle a single value: preparing the slice in the caller; looping over the slice in the callee. I'm sure the compiler can do a good job of reducing the overhead, will it get clever enough to reduce it to zero?

Just as an illustration, this benchmark compares Add(string) vs. Add(...string) using a trivial implementation of a string set using a map[string]struct{}. Both functions are inlined. At tip, this gives me

name    old time/op  new time/op  delta
Add-12  10.9ns ± 5%  11.7ns ± 2%  +6.95%  (p=0.000 n=10+10)

[Merovius]

Fair enough. I find it surprising that there is a performance difference (albeit a small one, TBH), but I can't argue with the numbers. I was obviously making wrong assumptions.

[ianlancetaylor]

I think we should fix the performance difference. We shouldn't decide between single argument and variadic argument on the basis of performance, only on the basis of readability.

[cespare]

My main argument is that using variadic methods here is a worse API than using methods which take single values (so I wrote that down first and mentioned performance afterward).

However, I'm curious what it could mean to "fix" the performance difference. ISTM that the variadic methods imply passing values inside slices which inherently brings more complexity/instructions than passing a single value. Or are you positing some compiler optimization where it notices a variadic call with a single value and then "unrolls" the loop from the caller?

[ianlancetaylor]

My main argument is that using variadic methods here is a worse API than using methods which take single values (so I wrote that down first and mentioned performance afterward).

Right, sorry for misrepresenting.

But from a readability perspective I don't see much difference. s.Add(1) and s.Add(1, 2) both seem clear to me. Even s.Add(vals...) is reasonably clear. So to me the variadic API doesn't seem like it involves any extra complexity to the reader.

As far as performance goes, we need to teach the compiler to unroll a range loop over a known slice value with less than N elements where N is some value larger than 1. Then I assume the performance will be the same after inlining.

I expect it will look something like the following sequence of rewrites:

    s.Add(1, 2)
    s.Add([]int{1, 2}...)
    for _, v := range []int{1, 2} { s.m[v] = struct{}{} }
    s.m[1] = struct{}{}; s.m[2] = struct{}{}

[jba]

I would expect EqualFunc, as in maps.

[ianlancetaylor]

The proposed maps EqualFunc function uses the function to compare map values, not map keys. Sets have no values, only keys, so there is no need for EqualFunc.

[jba]

This proposal uses Has but Contains is used everywhere else (strings, bytes, the proposed slices). To be clear, I prefer Has on its own, but the inconsistency makes it harder to learn and I think that's more important.

[ianlancetaylor]

Switched to Contains.

[bcmills]

// Filter deletes any elements from s for which keep returns false.
func (s Set[Elem]) Filter(keep func(Elem) bool)

In functional programming, Filter has the connotation of returning a new data structure. Can we find a different name for this?

Personally, I like Prune — which, to me, carries the connotation of lopping off parts (of a plant) in-place.

[fzipp]

@bcmills With Prune I would expect the predicate function to be negated.

[Sajmani]

I was thinking Keep, which is the name of the function arg, too.

s.Keep(func(i int) {return i > 0})

[leighmcculloch]

The term keep doesn't tell me for sure that it isn't in place.

Could we have .Filter and .FilterInPlace? The first a copy, the second in place. It's clear.

Providing both copy and in place methods are common in some stdlibs. E.g. in Ruby there are both but functions that mutate typically have a ! as the last character in their name: filter, filter!. Having the two functions with similar names helps me understand the API.

[ianlancetaylor]

I'm leaning toward RemoveIf, which would be an in-place method.

I'm not sure we need a method that combines copying and removal. As this point that seems like a frill that we can consider adding if a lot of code winds up needing it.

[sbstp]

Rust names this functionality retain. The method name makes it obvious what it does and if the condition is negated or not.

[bcmills]

Parallel to #47330 (comment) for maps, would it make sense to reserve the Values() name for an iterator, and name the method that returns a slice something like ValueSlice() instead?

[cespare]

Or ToSlice or AsSlice or just Slice?

[leighmcculloch]

Instead of placing the slice function on the type could it live on the iterator? Values returns an iterator and then you can construct a slice from the iterator.

[bcmills]

@leighmcculloch, it could, but then we would have to define the iterator API before we could extract the values from a Set.

I think extracting the values as a slice is a common enough operation to merit its own method, and I don't think that this proposal necessarily needs to be gated on figuring out an entire ecosystem of “iterator” APIs.

[smyrman]

Are we sure we always want the method to allocate the slice? If we used append semantics, then both of the following would be supported:

set := New(1,2,3)
var slice []int
slice = set.AppendTo(slice)

Or:

set := New(1,2,3)
slice := set.AppendTo(nil)

You could at least imagine applications where this could be more efficient, as the end-user is offered the opportunity to control allocation if the code runs in a tight loop.

Not saying it's worth the trade-off. As a reference hash.Sum works with an append style interface, but it's also pretty confusing.

[DeedleFake]

In Java, it is often annoying that the various container types' add() methods are void. Although some of that annoyance is solved here by it being variadic, would it be possible for Add(), Remove(), and the like to return their own receiver? They'd still be in place, but that way something could be added and the set could be passed to something else in a single expression.

[ianlancetaylor]

That is not standard Go style, though. And speaking purely personally, I would it misleading that code like F(s.Add(1)) would modify s. It's much clearer that s is modified when the entire statement is s.Add(1).

[rsc]

I think the doc comment can be reduced to:

// A Set is a set of elements of some comparable type.
// The zero value of a Set is an empty set ready to use.
type Set[Elem comparable] struct {
    ... unexported fields ...
}

Calling sets "reference types" is confusing because they're not, at least as currently documented. They're just structs that happen to hold pointers, which is true of most Go types. We don't refer to them all as reference types.

Calling out that Sets cannot be modified concurrently from multiple goroutines is also confusing, because that's the default expectation for every Go data structure. We only document the deviations, when concurrent modifications are allowed.

(Compare list.List: it is just as much a "reference type" and is similarly safe to read but unsafe to modify from multiple goroutines, but we don't call attention to any of that. Or bytes.Buffer, which is also just as much a "reference type".)

Mentioning maps also encourages the reader to start thinking about questions like why isn't this a map or exactly how maps work. It is probably better to just let Sets be Sets.

[leighmcculloch]

The Set as proposed, relevant components below, does not have a convenient method for iteration.

type Set[Elem comparable] struct {
	// contains filtered or unexported fields
}

// Values returns the elements in the set s as a slice.
// The values will be in an indeterminate order.
func (s *Set[Elem]) Values() []Elem

// Do calls f on every element in the set s,
// stopping if f returns false.
// f should not change s.
// f will be called on values in an indeterminate order.
func (s *Set[Elem]) Do(f func(Elem) bool)

I see two approaches to iteration given the current API:

1. Using the Do method:

   Do allows you to provide a function that will be called for every element in the Set. This introduces a new pattern to iteration that isn't found in other types since iteration in Go in all other types are supported with a for range. This different pattern has some limitations.

   • It is not possible to return immediately from within an iteration. Instead, a value must be copied to a temporary variable and returned outside the iteration function, resulting in code that looks significantly different for iterating sets that other types. For example:

     func _() (Elem, bool) {
         set := set.Set{}
         // ...
         found := false
         var foundE Elem
         set.Do(func(e Elem) bool {
             if condition {
                 found = true
                 foundE = e
                 return false
             }
             return true
         })
         return foundE, found
     }

     I think it would be easier to work with map[key]struct{}. For example:

     func _() (Elem, bool) {
         set := map[Elem]struct{}{}
         // ...
         for v := range set {
             if condition {
                 return v, true
             }
         }
         return Elem{}, false
     }

   • Similar to the return example it is not possible to break out of higher up nested for's without a similar pattern.

2. Using the Values method and range:

   This approach doesn't share the disadvantages of the Do approach, but it comes at a cost since the Set is copied into a slice.

Could we include in this proposal a method of iterating Set using range? I understand this would be a language change and is therefore worthy of a separate proposal. I'm happy to open a new issue for it but I was holding off because it sounded like we'd get range for free with #47331 (comment) but that proposal has been retracted.