proposal: x/exp/maps: additional functionality, also a new package x/exp/sets #56128
Labels
Milestone
Comments
|
here it is: package sets
// Sets contain unique elements (keys). Effectively sets are implemented as
// key-only maps of empty structs: set[K] = map[K]struct{}
// Contains checks if there is a key in the set.
func Contains[S ~map[K]struct{}, K comparable](s S, k K) bool
// Contains checks if any of the keys is in the set.
func ContainsAny[S ~map[K]struct{}, K comparable](s S, keys ...K) bool
// Contains checks if all the keys are in the set.
func ContainsAll[S ~map[K]struct{}, K comparable](s S, keys ...K) bool
// Equal reports whether two sets contain the same keys.
func Equal[S1, S2 ~map[K]struct{}, K comparable](s1 S1, s2 S2) bool
// Clear removes all keys from s.
func Clear[S ~map[K]struct{}, K comparable](s S)
// Clone returns a copy of s.
func Clone[S ~map[K]struct{}, K comparable](s S) S
// Insert inserts the keys info s.
func Insert[S ~map[K]struct{}, K comparable](s S, keys ...K)
// Remove removes the keys from s.
func Remove[S ~map[K]struct{}, K comparable](s S, keys ...K)
// Union combines keys from s1 and s2 into one set.
// Returns s1 ∪ s2.
func Union[S map[K]struct{}, K comparable](s1 S, s2 S) S
// Merge inserts keys from src into the dst.
// Effectively, dst = dst ∪ src.
func Merge[S1 ~map[K]struct{}, S2 ~map[K]struct{}, K comparable](dst S1, src S2)
// Difference returns the keys from s1 that are not contained in s2.
// Returns s1 - s2.
func Difference[S map[K]struct{}, K comparable](s1 S, s2 S) S
// Subtract removes the src keys from the dst.
// Effectively, this is a difference (subtraction) operation: dst = dst - src.
func Subtract[S1 ~map[K]struct{}, S2 ~map[K]struct{}, K comparable](dst S1, src S2)
// Intersection returns keys that exist in both s1 and s2.
// Effectively: s1 ∩ s2
func Intersection[S map[K]struct{}, K comparable](s1 S, s2 S) S
// Intersect removes keys from dst that are not contained in src.
// Effectively, dst = dst ∩ src
func Intersect[S1 ~map[K]struct{}, S2 ~map[K]struct{}, K comparable](dst S1, src S2)
// Keys returns the keys from s as a slice. The keys will be in an
// indeterminate order.
func Keys[S ~map[K]struct{}, K comparable](s S) []K
// Sorted returns the keys from s as a sorted slice.
func Sorted[S ~map[K]struct{}, K constraints.Ordered](s S) []K
//-------------------------------------------
package maps
// Pair is a key-value pair that can be used to flatten maps.
type Pair[K any, V any] struct {
Key K
Val V
}
// Pairs returns a slice of key-value pairs constructed from m. The pairs will
// be in an indeterminate order.
func Pairs[M ~map[K]V, K comparable, V any](m M) []*Pair[K, V]
// SortedFunc returns a slice of key-value pairs constructed from m and sorted
// as determined by the less function. The sort is stable if the less function
// produces stable results.
func SortedFunc[M ~map[K]V, K comparable, V any](m M, less func(a, b *Pair[K, V]) bool) []*Pair[K, V]
// SortedByKey returns a slice of key-value pairs constructed from m and sorted
// by key. This sort is guaranteed to be stable because the keys are unique.
func SortedByKey[M ~map[K]V, K constraints.Ordered, V any](m M) []*Pair[K, V]
// SortedByKeyFunc returns a slice of key-value pairs constructed from m and
// sorted by key as determined by the less function. This sort is stable
// provided the less function produces stable results.
func SortedByKeyFunc[M ~map[K]V, K comparable, V any](m M, less func(a, b K) bool) []*Pair[K, V]
// SortedByVal returns a slice of key-value pairs constructed from m and sorted
// by value. This sort is stable only if there is no duplicates (all values are
// unique).
func SortedByVal[M ~map[K]V, K comparable, V constraints.Ordered](m M) []*Pair[K, V]
// SortedByValFunc returns a slice of key-value pairs constructed from m and
// sorted by value as determined by the less function. This sort is stable
// provided there is no duplicates (all values are unique) and the less function
// produces stable results.
func SortedByValFunc[M ~map[K]V, K comparable, V any](m M, less func(a, b V) bool) []*Pair[K, V]
// StableSortedByVal returns a slice of key-value pairs constructed from m and
// sorted by value. For duplicate values, sorting falls back to comparing keys.
// This sort is guaranteed to be stable.
func StableSortedByVal[M ~map[K]V, K constraints.Ordered, V constraints.Ordered](m M) []*Pair[K, V]
// SortedByValFunc returns a slice of key-value pairs constructed from m and
// sorted by value as determined by the less function. For duplicate values,
// sorting falls back to comparing keys. This sort is stable provided the less
// function produces stable results.
func StableSortedByValFunc[M ~map[K]V, K constraints.Ordered, V any](m M, less func(a, b V) bool) []*Pair[K, V]
// Insert copies key-value pairs into m, if the map doesn't already contain an
// elements with equivalent keys.
func Insert[M ~map[K]V, K comparable, V any](m M, pairs ...*Pair[K, V])
// InsertOrOverwrite copies key-value pairs into m, overwriting existing
// elements with equivalent keys.
func InsertOrOverwrite[M ~map[K]V, K comparable, V any](m M, pairs ...*Pair[K, V])
// KeySet returns a set constructed from all the keys in m.
func KeySet[M ~map[K]V, K comparable, V any](m M) map[K]struct{}
// Sliced returns elements from m that exist in s.
func Sliced[M ~map[K]V, S ~map[K]struct{}, K comparable, V any](m M, s S) M
// Merge copies key/value pairs in src adding them to dst. When a key from src
// is already in dst and the associated values are different, instead of
// overwriting, the whole key/value pair from src is copied to conflicts.
//
// Upon completion of this routine, the caller may analyze the conflicted keys
// and:
//
// - Discard and reject the conflicts
// - Overwrite the dst, for example by calling golang.org/x/exp/maps.Copy routine
// - Implement more granular solution by merging each value individually
//
func Merge[M1 ~map[K]V, M2 ~map[K]V, K comparable, V comparable](dst M1, src M2) (conflicts M2)
// MergeFunc provides the same functionality as Merge, but uses the allow
// functor to determine if a value can be overwritten.
func MergeFunc[M1 ~map[K]V, M2 ~map[K]V, K comparable, V any](dst M1, src M2, allow func(dstval, srcval V) bool) (conflicts M2)
// CalcMerge calculates statistics for merging src into dst.
//
// - Data in both dst ad src remains unchanged
// - Statistics is returned as sets of keys `map[K]struct{}`
// - Keys in src that are not in dst are returned in the `create` set
// - Keys/value pairs that are equal in both src and dst are returned in the `overwrite` set
// - Keys that have different values in src and dst are returned in the `conflicts` set
//
func CalcMerge[M1 ~map[K]V, M2 ~map[K]V, K comparable, V comparable](dst M1, src M2) (create, overwrite, conflicts map[K]struct{})
// CalcMergeFunc provides the same functionality as CalcMerge, but uses the
// allow functor to determine if a value can be overwritten. Notice also, that
// both dst and src maps in CalcMergeFunc are allowed to have different value
// types, which can help in merging heterogeneous data.
func CalcMergeFunc[M1 ~map[K]V1, M2 ~map[K]V2, K comparable, V1, V2 any](dst M1, src M2, allow func(key K, dstval V1, srcval V2) bool) (create, overwrite, conflicts map[K]struct{})
// ValueSet returns a set constructed from all the values in m.
func ValueSet[M ~map[K]V, K comparable, V comparable](m M) map[V]struct{}
// HasDuplicates checks whether m contains duplicates (multiple keys having the
// same value).
func HasDuplicates[M ~map[K]V, K comparable, V comparable](m M) bool
// Inverted produces inverted map from m. Entries that can not be inverted are
// returned as a set of duplicates, they are excluded from the inverted result.
//
// A strategy for resolving the issues with duplicates then may include
// iterating over the returned set of duplicates, possibly calling the
// MatchValue function to discover which keys are associated to each duplicate
// and taking appropriate actions.
//
func Inverted[M ~map[K]V, K comparable, V comparable](m M) (inverted map[V]K, duplicates map[V]struct{})
// MatchValue returns a set of keys that contain the same value v.
func MatchValue[M ~map[K]V, K comparable, V comparable](m M, v V) (keys map[K]struct{}) |
|
also, here are some of the examples: func ExampleInsert() {
m := map[int]string{
1: "one",
2: "two",
3: "three",
6: "six",
}
type pair = Pair[int, string]
Insert(m, &pair{3, "THREE"}, &pair{4, "FOUR"})
m2 := map[int]string{
1: "UNO",
2: "DOS",
3: "TRES",
5: "CINCO",
}
Insert(m, Pairs(m2)...)
for _, p := range SortedByKey(m) {
fmt.Printf("%d: %s\n", p.Key, p.Val)
}
// Output:
// 1: one
// 2: two
// 3: three
// 4: FOUR
// 5: CINCO
// 6: six
}
func ExampleInsertOrOverwrite() {
m := map[int]string{
1: "one",
2: "two",
3: "three",
6: "six",
}
type pair = Pair[int, string]
InsertOrOverwrite(m, &pair{3, "THREE"}, &pair{4, "FOUR"})
m2 := map[int]string{
1: "UNO",
2: "DOS",
3: "TRES",
5: "CINCO",
}
InsertOrOverwrite(m, Pairs(m2)...)
for _, p := range SortedByKey(m) {
fmt.Printf("%d: %s\n", p.Key, p.Val)
}
// Output:
// 1: UNO
// 2: DOS
// 3: TRES
// 4: FOUR
// 5: CINCO
// 6: six
}
func ExampleSortedByKey() {
m := map[int]string{
1: "one",
2: "two",
3: "three",
4: "four",
}
for _, p := range SortedByKey(m) {
fmt.Printf("%d: %s\n", p.Key, p.Val)
}
// Output:
// 1: one
// 2: two
// 3: three
// 4: four
}
func ExampleStableSortedByVal() {
m := map[int]string{
1: "D",
2: "C",
3: "B",
4: "A",
}
for _, p := range StableSortedByVal(m) {
fmt.Printf("%d: %s\n", p.Key, p.Val)
}
// Output:
// 4: A
// 3: B
// 2: C
// 1: D
}
func ExampleSliced() {
m := map[int]string{
1: "one",
2: "two",
3: "three",
4: "four",
}
s := map[int]struct{}{
2: {},
4: {},
}
for _, p := range SortedByKey(Sliced(m, s)) {
fmt.Printf("%d: %s\n", p.Key, p.Val)
}
// Output:
// 2: two
// 4: four
}
func ExampleMerge() {
m := map[int]string{
1: "one",
2: "two",
3: "three",
4: "four",
}
m2 := map[int]string{
2: "TWO",
3: "THREE",
4: "four",
5: "five",
}
conflicts := Merge(m, m2)
fmt.Printf("\nMERGED\n")
for _, p := range SortedByKey(m) {
fmt.Printf("%d: %s\n", p.Key, p.Val)
}
fmt.Printf("\nCONFLICTS\n")
for _, p := range SortedByKey(conflicts) {
fmt.Printf("%d: %s\n", p.Key, p.Val)
}
// Output:
//
// MERGED
// 1: one
// 2: two
// 3: three
// 4: four
// 5: five
//
// CONFLICTS
// 2: TWO
// 3: THREE
}
func ExampleInverted() {
m := map[string]int{
"one": 1,
"two": 2,
"three": 3,
"fourty two": 42,
"the answer to everything": 42,
}
inverted, duplicates := Inverted(m)
fmt.Printf("\nINVERTED\n")
for _, p := range SortedByKey(inverted) {
fmt.Printf("%d: %s\n", p.Key, p.Val)
}
fmt.Printf("\nDUPLICATES\n")
for v := range duplicates {
matching_keys := MatchValue(m, v)
as_slice := sets.Sorted(matching_keys)
fmt.Printf("%d: %s\n", v, strings.Join(as_slice, ", "))
}
// Output:
//
// INVERTED
// 1: one
// 2: two
// 3: three
//
// DUPLICATES
// 42: fourty two, the answer to everything
} |
|
Thanks. That is a lot of API. These days we would normally start a discussion for something like that. Or write a series of issues for changes. See, for example, #54012 or #54454. We're unlikely simply pick up a large package and add it to the standard library or even x/exp. But of course you can publish your package and encourage people to use it. Getting adopters is one of the best signals that a package is worth adding to the standard library. |
|
I agree, it looks a bit overwhelming. Keep in mind, however that things are well separated and can be easily sliced into completely independent modules:
(LOCs counts include comments) |
|
We already have a maps package. If there is a specific function that you can motivate then feel free to file a proposal, but it's overwhelming to have a proposal to add so many functions. That's almost certainly not the right thing to do on its own. |
|
This proposal has been added to the active column of the proposals project |
|
For your convenience, here is the summary split by functionality:
Sets
// Contains checks if there is a key in the set.
func Contains[S ~map[K]struct{}, K comparable](s S, k K) bool
// Contains checks if any of the keys is in the set.
func ContainsAny[S ~map[K]struct{}, K comparable](s S, keys ...K) bool
// Contains checks if all the keys are in the set.
func ContainsAll[S ~map[K]struct{}, K comparable](s S, keys ...K) bool
// Equal reports whether two sets contain the same keys.
func Equal[S1, S2 ~map[K]struct{}, K comparable](s1 S1, s2 S2) bool
// Clear removes all keys from s.
func Clear[S ~map[K]struct{}, K comparable](s S)
// Clone returns a copy of s.
func Clone[S ~map[K]struct{}, K comparable](s S) S
// Insert inserts the keys info s.
func Insert[S ~map[K]struct{}, K comparable](s S, keys ...K)
// Remove removes the keys from s.
func Remove[S ~map[K]struct{}, K comparable](s S, keys ...K)
// Union combines keys from s1 and s2 into one set.
// Returns s1 ∪ s2.
func Union[S ~map[K]struct{}, K comparable](s1 S, s2 S) S
// Merge inserts keys from src into the dst.
// Effectively, dst = dst ∪ src.
func Merge[S1 ~map[K]struct{}, S2 ~map[K]struct{}, K comparable](dst S1, src S2)
// Difference returns the keys from s1 that are not contained in s2.
// Returns s1 - s2.
func Difference[S ~map[K]struct{}, K comparable](s1 S, s2 S) S
// Subtract removes the src keys from the dst.
// Effectively, this is a difference (subtraction) operation: dst = dst - src.
func Subtract[S1 ~map[K]struct{}, S2 ~map[K]struct{}, K comparable](dst S1, src S2)
// Intersection returns keys that exist in both s1 and s2.
// Effectively: s1 ∩ s2
func Intersection[S ~map[K]struct{}, K comparable](s1 S, s2 S) S
// Intersect removes keys from dst that are not contained in src.
// Effectively, dst = dst ∩ src
func Intersect[S1 ~map[K]struct{}, S2 ~map[K]struct{}, K comparable](dst S1, src S2)
// Keys returns the keys from s as a slice. The keys will be in an
// indeterminate order.
func Keys[S ~map[K]struct{}, K comparable](s S) []K
// Sorted returns the keys from s as a sorted slice.
func Sorted[S ~map[K]struct{}, K constraints.Ordered](s S) []KMap Inversion
// ValueSet returns a set constructed from all the values in m.
func ValueSet[M ~map[K]V, K comparable, V comparable](m M) map[V]struct{}
// HasDuplicates checks whether m contains duplicates (multiple keys having the
// same value).
func HasDuplicates[M ~map[K]V, K comparable, V comparable](m M) bool
// Inverted produces inverted map from m. Entries that can not be inverted are
// returned as a set of duplicates, they are excluded from the inverted result:
//
// A strategy for resolving the issues with duplicates then may include
// iterating over the returned set of duplicates, possibly calling the
// MatchValue function to discover which keys are associated to each duplicate
// and taking appropriate actions.
//
func Inverted[M ~map[K]V, K comparable, V comparable](m M) (inverted map[V]K, duplicates map[V]struct{})
// MatchValue returns a set of keys that contain the same value v.
func MatchValue[M ~map[K]V, K comparable, V comparable](m M, v V) (keys map[K]struct{})Map Merging
// Merge copies key/value pairs in src adding them to dst. When a key from src
// is already in dst and the associated values are different, instead of
// overwriting, the whole key/value pair from src is copied to conflicts.
//
// Upon completion of this routine, the caller may analyze the conflicted keys
// and:
//
// - Discard and reject the conflicts
// - Overwrite the dst, for example by calling golang.org/x/exp/maps.Copy routine
// - Implement more granular solution by merging each value individually
//
func Merge[M1 ~map[K]V, M2 ~map[K]V, K comparable, V comparable]
(dst M1, src M2) (conflicts M2)
// MergeFunc provides the same functionality as Merge, but uses the allow
// functor to determine if a value can be overwritten.
func MergeFunc[M1 ~map[K]V, M2 ~map[K]V, K comparable, V any]
(dst M1, src M2, allow func(dstval, srcval V) bool) (conflicts M2)
// CalcMerge calculates statistics for merging src into dst.
//
// - Data in both dst and src remains unchanged
// - Statistics is returned as sets of keys `map[K]struct{}`
// - Keys in src that are not in dst are returned in the `create` set
// - Keys/value pairs that are equal in both src and dst are returned in the `overwrite` set
// - Keys that have different values in src and dst are returned in the `conflicts` set
//
func CalcMerge[M1 ~map[K]V, M2 ~map[K]V, K comparable, V comparable]
(dst M1, src M2) (create, overwrite, conflicts map[K]struct{})
// CalcMergeFunc provides the same functionality as CalcMerge, but uses the
// allow functor to determine if a value can be overwritten. Notice also, that
// both dst and src maps in CalcMergeFunc are allowed to have different value
// types, which can help in merging heterogeneous data.
func CalcMergeFunc[M1 ~map[K]V1, M2 ~map[K]V2, K comparable, V1, V2 any]
(dst M1, src M2, allow func(key K, dstval V1, srcval V2) bool) (create, overwrite, conflicts map[K]struct{})Key-Value Pairs
// Pair is a key-value pair that can be used to flatten maps.
type Pair[K any, V any] struct {
Key K
Val V
}
// Pairs returns a slice of key-value pairs constructed from m. The pairs will
// be in an indeterminate order.
func Pairs[M ~map[K]V, K comparable, V any](m M) []*Pair[K, V]
// SortedFunc returns a slice of key-value pairs constructed from m and sorted
// as determined by the less function. The sort is stable if the less function
// produces stable results.
func SortedFunc[M ~map[K]V, K comparable, V any](m M, less func(a, b *Pair[K, V]) bool) []*Pair[K, V]
// SortedByKey returns a slice of key-value pairs constructed from m and sorted
// by key. This sort is guaranteed to be stable because the keys are unique.
func SortedByKey[M ~map[K]V, K constraints.Ordered, V any](m M) []*Pair[K, V]
// SortedByKeyFunc returns a slice of key-value pairs constructed from m and
// sorted by key as determined by the less function. This sort is stable
// provided the less function produces stable results.
func SortedByKeyFunc[M ~map[K]V, K comparable, V any](m M, less func(a, b K) bool) []*Pair[K, V]
// SortedByVal returns a slice of key-value pairs constructed from m and sorted
// by value. This sort is stable only if there is no duplicates (all values are
// unique).
func SortedByVal[M ~map[K]V, K comparable, V constraints.Ordered](m M) []*Pair[K, V]
// SortedByValFunc returns a slice of key-value pairs constructed from m and
// sorted by value as determined by the less function. This sort is stable
// provided there is no duplicates (all values are unique) and the less function
// produces stable results.
func SortedByValFunc[M ~map[K]V, K comparable, V any](m M, less func(a, b V) bool) []*Pair[K, V]
// StableSortedByVal returns a slice of key-value pairs constructed from m and
// sorted by value. For duplicate values, sorting falls back to comparing keys.
// This sort is guaranteed to be stable.
func StableSortedByVal[M ~map[K]V, K constraints.Ordered, V constraints.Ordered](m M) []*Pair[K, V]
// SortedByValFunc returns a slice of key-value pairs constructed from m and
// sorted by value as determined by the less function. For duplicate values,
// sorting falls back to comparing keys. This sort is stable provided the less
// function produces stable results.
func StableSortedByValFunc[M ~map[K]V, K constraints.Ordered, V any](m M, less func(a, b V) bool) []*Pair[K, V]
// Insert copies key-value pairs into m, if the map doesn't already contain an
// elements with equivalent keys.
func Insert[M ~map[K]V, K comparable, V any](m M, pairs ...*Pair[K, V])
// InsertOrOverwrite copies key-value pairs into m, overwriting existing
// elements with equivalent keys.
func InsertOrOverwrite[M ~map[K]V, K comparable, V any](m M, pairs ...*Pair[K, V])
// KeySet returns a set constructed from all the keys in m.
func KeySet[M ~map[K]V, K comparable, V any](m M) map[K]struct{}
// Sliced returns elements from m that exist in s.
func Sliced[M ~map[K]V, S ~map[K]struct{}, K comparable, V any](m M, s S) M |
|
As I noted two weeks ago, this proposal is too large. If there are specific changes to make, please file separate proposals. Please do NOT file 20 proposals. Focus on the specific changes you think are most important. |
|
Based on the discussion above, this proposal seems like a likely decline. |
|
No change in consensus, so declined. |
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
I written a little generics library with a couple of packages to deal with maps and sets. Basically extensions to
x/exp/mapsand also a separateslicespackage.I think this library falls within the scope of
x/exp/*and I am willing to donate the code.Here is the link: https://github.com/adnsv/go-exp
github.com/adnsv/go-exp/mapspackagegithub.1485827954.workers.dev/adnsv/go-exp/setspackageThere is nothing particularly revolutionary there, but I find it extremely helpful in dramatically reducing the amount of boiler plate code often ending up with one-liners with nice descriptive names which are easy to understand.
If you have a chance, please review it. It has a few usage examples and tests implemented.
The text was updated successfully, but these errors were encountered: