Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: x/exp/maps: add Merge #52806

Closed
moskyb opened this issue May 9, 2022 · 8 comments
Closed

proposal: x/exp/maps: add Merge #52806

moskyb opened this issue May 9, 2022 · 8 comments

Comments

@moskyb
Copy link

moskyb commented May 9, 2022

The new x/exp/maps package covers most of the things i really wanted generics for with maps (🙏 Keys and Values), but the other thing i find myself doing with generic maps a lot is merging two (or more) maps into one larger map. IMO it's a common enough task to get integrated into the maps package.

My proposed implentation is:

func Merge[M ~map[K]V, K comparable, V any](maps ...M) M {
	fullCap := 0
	for _, m := range maps {
		fullCap += len(m)
	}

	merged := make(M, fullCap)
	for _, m := range maps {
		for key, val := range m {
			merged[key] = val
		}
	}

	return merged
}

Happy for this implementation to be changed, it's what i came up with in about 5 minutes, i'm sure it can be improved 😅

It'd be probably worth calling out in the docs, like we do for Copy, that this is only a shallow merge and that it won't traverse deeper map map elements to try to merge them.

@moskyb moskyb added the Proposal label May 9, 2022
@gopherbot gopherbot added this to the Proposal milestone May 9, 2022
@ianlancetaylor ianlancetaylor added this to Incoming in Proposals (old) May 9, 2022
@rsc
Copy link
Contributor

rsc commented May 11, 2022

It seems like Merge is a variadic repeated Copy into a new map? This doesn't seem like it comes up enough to put into the standard library.

@rsc rsc moved this from Incoming to Active in Proposals (old) May 11, 2022
@rsc
Copy link
Contributor

rsc commented May 11, 2022

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

@moskyb
Copy link
Author

moskyb commented May 11, 2022

Anecdotally, I've had to implement this in the vast majority of go projects I've worked on - it comes up pretty often. In terms of data, I cobbled together this sourcegraph search, which has a couple of false positives, but indicates that a function like this is pretty fairly implemented.

In terms of variadicity (is that a word?) almost all of the time i'll just implement merge on two maps, eg

func Merge[M ~map[K]V, K comparable, V any](this, that M) M {
	merged := make(M, len(this) + len(that))
	for _, m := range maps {
		for key, val := range m {
			merged[key] = val
		}
	}

	return merged
}

but i figured in this case that adding the variadicity was a nice usability improvement, and made the method more usable in a stdlib use case.

I know that we don't implement the Go Standard Library based on what other languages are doing, but it's a point of reference that methods like this are useful enough to go in the stdlibs of a lot of other languages (see: Ruby's Hash#merge, Java's Map::putAll and Rust's HashMap.extend). This is a pretty common thing to do with maps.

@ainar-g
Copy link
Contributor

ainar-g commented May 12, 2022

I feel like a map merge, as opposed to a set merge, would need a way to define the way of resolving key conflicts. That is, if maps m1 and m2 have different values set with the same key, which one should remain in the resulting map?

(As an aside, a few of the maps in the Sourcegraph search seem to be map[T]struct{} and map[T]bool, which means that they're really sets, and fwiw, any generic set package must include the union operation.)

@moskyb
Copy link
Author

moskyb commented May 12, 2022

Given the prevalence of the Operation and OperationFunc pattern within the slices package (eg. Equal and EqualFunc, etc), i don't see a reason why we couldn't have both, letting the default be "values in later maps overwrite values in earlier ones":

package maps

func Merge[M ~map[K]V, K comparable, V any](maps ...M) M {
	fullCap := 0
	for _, m := range maps {
		fullCap += len(m)
	}

	merged := make(M, fullCap)
	for _, m := range maps {
		for key, val := range m {
			merged[key] = val
		}
	}

	return merged
}

func MergeFunc[M ~map[K]V, K comparable, V any](conflictFunc func(V, V) V, maps ...M) M {
	fullCap := 0
	for _, m := range maps {
		fullCap += len(m)
	}

	merged := make(M, fullCap)
	for _, m := range maps {
		for key, val := range m {
			if v, ok := merged[key]; ok {
				merged[key] = conflictFunc(v, val)
				continue
			}
			merged[key] = val
		}
	}

	return merged	
}

This way, we could have something like:

m1 := map[string]int{"a": 1, "b": 2, "c": 3}
m2 := map[string]int{"b": 2, "e": 0}
MergeFunc(func(a, b int) int { return a + b }, m1, m2) // => map[string]int{"a": 1, "b": 4, "c": 3, "e": 0}

Admittedly this sort of breaks the established pattern of having the funcs be the last argument, as the maps argument is variadic, but i also don't want to nail down an implementation prematurely, I'm more interested in establishing if other people actually think that this is a good idea

@rsc
Copy link
Contributor

rsc commented May 18, 2022

It's still unclear why we need to add Merge when we have Copy. Instead of Merge(m1, m2) you can do

out := make(map[...]...)
maps.Copy(out, m1)
maps.Copy(out, m2)

I didn't look super closely at the sourcegraph results but skimming through the first one that jumped out at me

https://sourcegraph.com/github.com/pachyderm/pachyderm/-/blob/src/server/pps/server/api_server.go?L107

was just Copy (MergeInto), not Merge.

@moskyb
Copy link
Author

moskyb commented May 19, 2022

oh shivers - i had
A) Not RTFM and noticed the maps.Copy method, and
B) Thought you were referring to the builtin copy() method.

I'm a dummy, i'm gonna close this issue.

@moskyb moskyb closed this as completed May 19, 2022
@rsc rsc moved this from Active to Declined in Proposals (old) May 25, 2022
@rsc
Copy link
Contributor

rsc commented May 25, 2022

This proposal has been declined as retracted.
— rsc for the proposal review group

@golang golang locked and limited conversation to collaborators May 25, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
No open projects
Development

No branches or pull requests

4 participants