proposal: x/exp/maps: add Merge

[moskyb]

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.

[rsc]

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]

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]

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]

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]

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]

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]

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.

[rsc]

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