proposal: go/types: add set data type

[andybbruno]

Hi there,

I'd like to propose the addition of a set data type to the go/types package. Sets are a fundamental data structure widely used in various applications for efficient membership testing and eliminating duplicates. By introducing a native set type, we can simplify code, improve readability, and enhance performance.

Motivation:

1. Simplicity: Currently, developers often implement sets using maps or slices, resulting in boilerplate code and reduced clarity. A built-in set type would streamline this process.

2. Performance: A dedicated set type can be optimized for common set operations like membership checks, union, intersection, and difference, leading to improved runtime efficiency.

3. Code Readability: Introducing a set type would enhance code readability by making intentions clearer and reducing the need for workarounds.

Design:

1. The set type can be implemented as a wrapper around a map with an empty struct type (map[T]struct{}), where T represents the element type.

2. Methods can include Add, Remove, Contains, Union, Intersection, and Difference, providing a comprehensive set of operations.

3. Compatibility with the existing range loop can be achieved by making the set type implement the Iterable interface.

Example Usage:

package main

import (
	"fmt"
	"go/types"
)

func main() {
	s := types.NewSet()
	s.Add(1, 2, 3)
	s.Add(3, 4, 5)

	if s.Contains(2) {
		fmt.Println("Set contains 2")
	}

	// More operations...
}

Impact:
The introduction of a native set type in the go/types package would lead to more idiomatic and efficient Go code, benefiting both new and experienced developers. It would also align with Go's philosophy of simplicity and efficiency.

Thanks,
Andrea Bruno

[Jorropo]

go/types implements the go type system, this is useful if you are writing compilers, linters, ... it has nothing to do with types for programs. The representation of your set type in go/types would be as instance of go/types.Struct.
You should really find an other place for it, like a new package such as set idk.

map[T]struct{} usually gets the job done for me, if set would use runtime hooks to provide more efficient implementations of Union, Intersection, and Difference this could be interesting.

[andybbruno]

Hi @Jorropo thanks for your opinion.

I understand your concern about where to place the set functionality. However, I believe the focus should be on having a native set data structure in Go, which can enhance code readability and performance. Whether it’s in the go/types package or a separate one, the important thing is to provide developers with this useful tool.

[fzipp]

Please see this previous discussion: #47331
A proposal for a set data type depends on the outcome of the iteration proposal #61405.

[seankhliao]

I'm going to mark this as a dup of the previous discussion.
A more fully fleshed out proposal can come later

[seankhliao]

Duplicate of #47331