proposal: maps: new package to provide generic map functions (discussion)

[ianlancetaylor]

This is a discussion that led to the proposal #47649.

This proposal is for use with #43651. We propose defining a new package, maps, that will provide functions that may be used with maps of any type. If this proposal is accepted, the new package will be included with the first release of Go that implements #43651 (we currently expect that that will be Go 1.18).

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).

// Package maps defines various functions useful with maps of any type.
package maps

// Keys returns the keys of the map m.
// The keys will be an indeterminate order.
func Keys[M constraints.Map[K, V], K comparable, V any](m M) []K

// Values returns the values of the map m.
// The values will be in an indeterminate order.
func Values[M constraints.Map[K, V], K comparable, V any](m M) []V

// Equal reports whether two maps contain the same key/value pairs.
// Values are compared using ==.
func Equal[M1, M2 constraints.Map[K, V], K, V comparable](m1 M1, m2 M2) bool

// EqualFunc is like Equal, but compares values using cmp.
// Keys are still compared with ==.
func EqualFunc[M1 constraints.Map[K, V1], M2 constraints.Map[K, V2], K comparable, V1, V2 any](m1 M1, m2 M2, cmp func(V1, V2) bool) bool

// Clear removes all entries from m, leaving it empty.
func Clear[M constraints.Map[K, V], K comparable, V any](m M)

// Clone returns a copy of m.  This is a shallow clone:
// the new keys and values are set using ordinary assignment.
func Clone[M constraints.Map[K, V], K comparable, V any](m M) M

// Copy copies all key/value pairs in src adding them to dst.
// When a key in src is already present in dst,
// the value in dst will be overwritten by the value associated
// with the key in src.
func Copy[M constraints.Map[K, V], K comparable, V any](dst, src M)

// DeleteFunc deletes any key/value pairs from m for which del returns true.
func DeleteFunc[M constraints.Map[K, V], K comparable, V any](m M, del func(K, V) bool)

[rsc]

DeleteIf still doesn't feel exactly right to me. It occurs to me that slices, bytes, and strings all have a precedent for this kind of thing already: IndexFunc, ContainsFunc, and so on. It sure seems like slices.Index is to slices.IndexFunc as maps.Delete is to __this function__, which suggests it should be called DeleteFunc.

Here are all the functions taking functions as arguments in the standard library:

% grep -h 'func .*, func' go/api/* | sort
pkg bytes, func FieldsFunc([]uint8, func(int32) bool) [][]uint8
pkg bytes, func IndexFunc([]uint8, func(int32) bool) int
pkg bytes, func LastIndexFunc([]uint8, func(int32) bool) int
pkg bytes, func TrimFunc([]uint8, func(int32) bool) []uint8
pkg bytes, func TrimLeftFunc([]uint8, func(int32) bool) []uint8
pkg bytes, func TrimRightFunc([]uint8, func(int32) bool) []uint8
pkg crypto, func RegisterHash(Hash, func() hash.Hash)
pkg flag, func Func(string, string, func(string) error)
pkg go/ast, func Inspect(Node, func(Node) bool)
pkg go/parser, func ParseDir(*token.FileSet, string, func(os.FileInfo) bool, Mode) (map[string]*ast.Package, error)
pkg image, func RegisterFormat(string, string, func(io.Reader) (Image, error), func(io.Reader) (Config, error))
pkg math/rand, func Shuffle(int, func(int, int))
pkg net/http, func HandleFunc(string, func(ResponseWriter, *Request))
pkg os, func Expand(string, func(string) string) string
pkg reflect, func MakeFunc(Type, func([]Value) []Value) Value
pkg runtime/pprof, func Do(context.Context, LabelSet, func(context.Context))
pkg runtime/pprof, func ForLabels(context.Context, func(string, string) bool)
pkg runtime/trace, func WithRegion(context.Context, string, func())
pkg sort, func Search(int, func(int) bool) int
pkg sort, func Slice(interface{}, func(int, int) bool)
pkg sort, func SliceIsSorted(interface{}, func(int, int) bool) bool
pkg sort, func SliceStable(interface{}, func(int, int) bool)
pkg strings, func FieldsFunc(string, func(int32) bool) []string
pkg strings, func IndexFunc(string, func(int32) bool) int
pkg strings, func LastIndexFunc(string, func(int32) bool) int
pkg strings, func TrimFunc(string, func(int32) bool) string
pkg strings, func TrimLeftFunc(string, func(int32) bool) string
pkg strings, func TrimRightFunc(string, func(int32) bool) string
pkg testing, func AllocsPerRun(int, func()) float64
pkg time, func AfterFunc(Duration, func()) *Timer
% 

Obviously many of these aren't analogous, but the ones are analogous overwhelmingly use FooFunc.
And there's nothing at all ending in a conjunction like DeleteIf.
In particular it's not ContainsIf or IndexIf.

I suggest we use DeleteFunc.

[deanveloper]

I’m largely in support of this, but I think my only opposition to this is that the “XyzFunc” pattern typically just means “the exact same as Xyz but uses a function”. However, DeleteFunc isn’t the exact same as delete, since it may be (and will likely be used for) deleting more than one element.

[bcmills]

@deanveloper, you could file a proposal to make the delete built-in variadic. 😁

[benhoyt]

I'm concerned about the complexity of these function signatures. It's definitely better now that we can use ~map[K]V instead of constraints.Map[K, V] (see the current version of maps.go), but the function signatures, which of course will be shown in some fashion in the package docs, are rather unwieldy -- they remind me of Scala, and that's not a place I want Go to go.

For reference, here's the current signature:

func Keys[M ~map[K]V, K comparable, V any](m M) []K { ... }

The simpler signature:

func Keys[K comparable, V any](m map[K]V) []K { ... }

Will be simpler to read in the docs, and actually uses map[K]V in the main parameter list so is easier to understand conceptually. The simpler version works fine with ordinary maps and with named types whose underlying type is a map (see here).

The only downside it has is what @Merovius pointed out above -- if you need to instantiate or pass around a function of the concrete type. (An example @rogpeppe showed me is here). As Axel acknowledged above, "it's a bit of a stretch". I think this will be very rare, and I believe doesn't warrant complicating the signatures -- normal use will just be a type-inferred call like maps.Keys(m). Besides, in the rare cases you need to instantiate the concrete function type, you can write a one-line wrapper function to get it.

The only function that really needs it is Clone, as it returns a map. I don't mind keeping that one as is -- I think it would be better to have 7 simpler signatures and 1 more complex one than 8 more complex (consistent) ones. And you could even rotate the M type to the end in Clone so the K comparable, V any type parameters are first for all of them. We could add a sentence to the Clone doc to explain something like "M is constrained to ~map[K]V so that the returned map has the same type as map being cloned, even if a named map type is being used" or similar (this wasn't obvious to me at first).

There was discussion about avoiding constraints.Map above (which is no longer needed, phew), but the thread above kind of devolved into a syntax discussion, which we're understandably not going to change at this point. So I'd love it if we can discuss simplifying the signatures specifically.

[bcmills]

I can see the benefit to Keys and Values, but I wonder if we're going to have support for more general iterators in the future.

Thinking ahead to that, should we name these functions KeySlice and ValueSlice instead, so that we can retains the nicer Keys and Values names for iterators?

[colin-sitehost]

Fair, "drift in a functional direction" is what I meant and that is present in rust, kotlin, and haskell.

I meant other code that currently returns a slice that will be iterated over in the future, e.g. iter.From(fetchSlice()), but I see what you are saying: this would be an iterator that loops over the map without allocating. Still of a mind that we should plan for today and not worry too much about what iterators would look like, since there is not even a proposal,maps.KeyIter(m) is not too bad, and it is explicit about the iterator part.

[pcman312]

What does an iterator provide over a for loop?

[DeedleFake]

It's like the difference between a file handle and an io.Reader, except maybe a bit more so. Iterators are like generecized pieces of a loop that can be passed around and wrapped with other pieces in a middleware-esque fashion.

[Merovius]

@pcman312 The ability to be implemented by a user of the language.

[ianlancetaylor]

A normal map iterator will be over key/value pairs. I don't think that an iterator over just keys or just values will be the common case. While I can imagine adding them (if we ever have iterators), I don't think we need to reserve better names for them.

[sbstp]

[ Resolved -- out of scope for this proposal ]

I think it would be extremely valuable if the standard library contained a standardized iterator interface, something like:

type Iterator[T any] interface {
    // Next returns true until there are no more elements in this iterator.
    func Next() bool
    // Value returns the current value of this iterator.
    func Value() T
}

It would allow to get the keys or values of a map without allocating a slice.

keys := maps.Keys(myMap);
for keys.Next() {
    fmt.Println(keys.Value())
}

If putting the values in a slice is required, a function to do this can be created easily in the slices package.

func Collect[T any](it Iterator[T]) []T {
    var result []T
    for it.Next() {
        result = append(result, it.Value())
    }
    return result
}

I don't think language support for Iterators is necessary, but I think that defining a standard interface for them is a necessity. If no official interface for iterators is provided, it's almost certain that multiple implementations will pop up in 3rd party libraries and lead to fragmentation of the ecosystem.

Plus it allows us to create potentially less memory intensive programs by avoiding slice allocations.

[DeedleFake]

There's been some discussion of this elsewhere, including in this discussion as well as in #43557. Unfortunately, creating an iterator over a map in Go without language changes is surprisingly difficult, as the only way to iterate through one is with range, and that's incompatible with a Next() method based iterator without a background thread.

[sbstp]

Yeah it would require access to the functions in runtime/map.go

[Merovius]

@DeedleFake FWIW it doesn't need a language-change - after all, reflect.MapIter exists. But it does require cooperation from the runtime, which is why the stdlib is the only place where it could feasibly be done.

That being said, the idea of adding an iterator interface, as well as the idea to expose a concrete iterator over maps, have been rejected decisively, for go 1.18. It is not going to happen.

[ianlancetaylor]

Iterators are worth discussing in general, but please not on this proposal, which is about a proposed maps package. Thanks.

[rogpeppe]

it would be helpful to provide use-cases of where you use interfaces as key types.

One classic example is map[reflect.Type]T.

[Merovius]

Just realized: The top-comment doesn't use constraints.Map. That should probably be fixed.

[andig]

No offense (FTR, I'm not happy about it either) but I think the time for changes like this is past. Generics are clearly slated for release in go 1.18 - re-opening the syntax discussion doesn't work under that timeline.

I don‘t see a reason to release something that doesn‘t feel right. That the proposals have been approved should not mean that they should be rushed to any particular release.

[ianlancetaylor]

We've spent at least two years discussing the syntax. I don't think we are rushing into anything.

That said I hope that #48424 will help here.

[andig]

We've spent at least two years discussing the syntax. I don't think we are rushing into anything.

That said I hope that #48424 will help here.

Came here from that discussion. I didn‘t want to imply that things are rushed, just that an announced release should not force a functionality. Go is famous for doing things right or not at all and generics is a complex topic.

[go101]

I always think the minimum requirement for a generic design is builtin generics should be able to be defined by using the custom generic rules. For example, we could use a custom map type as TreeMap{Key]Value. It looks this is never a goal for the current design.

[ianlancetaylor]

@go101 That is true: that was not a goal. And this discussion, which is about the maps package, is not the place to discuss that. golang-nuts would be fine. Thanks.

[kelindar]

[ Resolved -- no ]

Would this also work with sync.Map?

[Merovius]

No. There is no way to write a generic function that works both on sync.Map and map[K]V.

[hherman1]

I wish we could figure out a way to make interchanging user built hash maps and std maps smooth before adding these utils, else we’ll probably see the same code rewritten many times for these things. I think we will probably end up with a GenericMap if we’re not careful that wraps built in map awkwardly just to fit in with user defined code that wants to be impl agnostic

[Merovius]

@hherman1 I think the way this will go at first is that if your package takes an interface for a map-like datastructure, you also provide a wrapper-type type Map[K comparable, V any] map[K]V which implements that interface using a builtin map. Users could then call your code as somepkg.F(somepkg.Map(m)). Not super ergonomic, but IMO okay. If we ever add an interface for a map-like datastructure in the stdlib, we can then also put such a wrapper-type alongside it.

FWIW for sync.Map specifically, I don't think the functions that are proposed here even make a lot of sense. Generally, sync.Map can be modified concurrently, so using operations that consider "the entire map" don't make a lot of sense for it.

[Merovius]

[ Resolved -- changed to Copy ]

I have a mild preference for renaming Add to Copy. The latter gives a clear analog to copy and io.Copy indicating the order of arguments, which is less clear for Add.

[rsc]

The builtin copy function seems key-based to me. It does

for i, v := range src { dst[i] = v }

which is exactly what this function would do.

[rsc]

I looked at what other languages call this operation.
I can't find it in Java at all.
Rust calls this operation extend (on all collections).
Swift has merge but it also takes a function to reduce duplicate values. In Go it would be

func merge(dst, src map[K]V, combine func(V,V)V) {
    for k, v := range src {
        if dv, ok := dst[k]; ok {
            dst[k] = combine(dv, v)
        } else {
            dst[k] = v
        }
    }
}

These are of course both methods, and x.extend(y) and x.merge(y) are clearer than extend(x, y) and merge(x, y).

In contrast, it really seems like Copy(x,y) is pretty clear given what programmers already know about slice copy and io.Copy.

[hherman1]

The Java name is putAll https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#putAll-java.util.Map-

[earthboundkid]

FWIW, JavaScript has Object.assign(a, b), which works like this. maps.Assign(m1, m2) is okay if not great.

[ianlancetaylor]

OK, going with Copy.

[jimmyfrasche]

[ Resolved -- changed to DeleteIf ]

Filter seems out of place since it was removed from the proposed slices package but is much easier to implement for maps.

I could see a func Remove[K comparable, V any](m map[K]V, keys ...K) for bulk deletions similar to the proposed Set package.

[Cyberax]

Users with that preconception will quickly realize the error in their mental model when they notice that Filter doesn't return anything at all.

There are libraries that use value-returning Filter methods. Why be different here? It doesn't gain anything useful except needlessly aggrieve users.

[Merovius]

@Cyberax Because the in-place version does not allocate and is (presumably) often what we want. You can still write maps.Filter(maps.Clone(m), keep) to not operate in-place, but if we'd only have the non-in-place version, you couldn't make an in-place version out of it. Though there might be a case to add both, as calling Clone and removing all filtered elements is slightly less efficient than creating an empty map and adding all kept elements.

[Cyberax]

I'm not arguing with having an in-place operation. Just name it something like RemoveIf or KeepIf. And both names are actually more descriptive.

An explicit cloning Filter method can be added later if needed.

[ianlancetaylor]

It looks like C++20 has this function but calls it erase_if. Since in Go we remove elements from a map using delete, that suggests that we name this function DeleteIf.

[ianlancetaylor]

Changed to DeleteIf.

[anjmao]

[ Resolved -- the existence of modules doesn't mean that the standard library is not needed ]

Now as Go supports modules I wonder why do you want to put these generic slices and maps packages into standard library. Why not putting it to golang.org/x/...?

[rsc]

Because they will be used by essentially all Go programs. They are core to Go.

[kevinburke]

Would you mind adding an example of what it would look like to use it?

[ianlancetaylor]

This comment didn't get threaded and I no longer remember what it referred to. Do you remember?

[Sandertv]

Having used the x/exp/maps package for a little, I feel like the type parameters for maps.Values() and maps.Keys() are a bit cumbersome when it comes to the comparable type parameters:
func Keys[M ~map[K]V, K comparable, V any](m M) []K
func Values[M ~map[K]V, K comparable, V any](m M) []V

It's not unusual to have an interface as key types in a map, which however immediately means not being able to use these functions. This requirement of having comparable keys seems unnecessary as well, given that no comparison is done in either of these functions.

I understand that this might boil down to the argument of comparable including interfaces or not, but it seems reasonable to accept any as the map keys to these functions as this comparability requirement doesn't exist for these functions. The existence of these maps guarantees that they have comparable keys anyway.

[Merovius]

See #51338 for some discussion about this problem. In particular, it would be helpful to provide use-cases of where you use interfaces as key types.

Note that the constraint has to be comparable to be able to even write map[K]V, even if you don't do any comparisons. So, at least for Go 1.18, this is where we're at - it's simply not possible to use generic maps with interface key types.

[Sandertv]

I did not know a constraint had to be comparable to be able to write map[K]V. In that case I rest my case here, as this was a specific comment for those methods. Thanks for clearing that up!

[DeedleFake]

[ Resolved -- leave for later ]

How about an Entries() method that returns a slice of some pair type of the keys and values? That pair type could be either something new in this package, such as just type Entry[K comparable, V any] struct { Key K; Value V }, or it could be some more general Pair type implemented somewhere else.

If that gets added, it might also make sense to add func Of[K comparable, V any](v ...Entry[K, V]) map[K]V for parity with both that and set.Of(). That seems less useful to me with a maps.Entry type rather than a generalized pair type, though, as it would specifically require a slice of Entrys. It could still be useful paired with some kind of iterator collection function, though.

[colin-sitehost]

While I agree, and I think a compelling case can be made for only adding pair [recte two tuple], it is not special and the need for a n tuples will begin to develop with generics. I do not want to block anything, but this is probably a good time to reconsider #32941, since imo this reads better:

func Entries[K comparable, V any](m map[K]V) [](K, V)

func Of[K comparable, V any](v ...(K, V)) map[K]V

Though, if we do not; I think the following convention is fairly readable:

func Entries[K comparable, V any](m map[K]V) []struct{K; V}

func Of[K comparable, V any](v ...struct{K; V}) map[K]V

[rsc]

Generally speaking, we are trying to limit the initial API to "clearly should be in this package", not just "probably okay".
This API strikes me as more the latter than the former.

[deanveloper]

[ Resolved -- leave for later ]

Along with the container/set discussion, an Any/Peek or Pop function would be nice. As said in the other discussion, I often do recursive algorithms with a base case of len(m)==1. Any/Peek would be best but a Pop would suffice too. Currently the only way to get the sole element of a map is to range, which is pretty inconvenient

[Merovius]

Retracted

---

I would like to propose adding

// Range returns a range iterator over m.
//
// Call Next to advance the iterator, and Key/Value to access each entry. Next
// returns false when the iterator is exhausted. Range follows the same
// iteration semantics as a range statement.
func Range[K comparable, V any, M constraints.Map[K, V]](m M) *Iter[K, V]`

// An Iter is an iterator for ranging over a map. See Range.
type Iter[K comparable, V any] struct {
    // Contains unexported fields
}

func (it *Iter[K, V]) Next() bool

func (it *Iter[K, V]) Key(p *K)

func (it *Iter[K, V]) Value(p *V)

Range and Iter would be type-safe versions of (reflect.Value).MapRange and reflect.MapIter respectively. The implementation would call into runtime for their implementation (and could hopefully be inlined, to be just as efficient as range).

On its own, this isn't very useful - we can just use range directly. However, it would enable us to get efficient, leak-free iterators of maps, which can be resumed and passed around. More importantly, this could be used by container/set to replace Do with a better API - allowing the user to use break and return early as needed without extra hoops to jump through and not having to worry about the closure escaping or anything like this.

It would also lay the groundwork for an iteration API - for example, a package could define

type Iter[V any] interface {
    Next() bool
    Value(p *V)
}

to be able to iterate over either a map or a container/set.Set and it would be an interface easily implemented by third-party collections as well.

Lastly, this is something that can't really be implemented outside of the stdlib. It requires interaction with the runtime and its implementation details.

[Merovius]

@komuw Maybe. See above about the interconnectedness of decisions, though. IMO the maps package seems the right place to put it, so that proposal would still be tied to the fate of this proposal. And then, the motivating factor of suggesting this (a better iteration API and more freedom about the type-definition for container/set) would depend both on this proposal and that new one.

So, I deliberately put the suggestion here, for better or for worse.

[Merovius]

@deanveloper I haven't read all the discussion of #43557 - but from the proposal text, it seems that can't be implemented for a map. That's what I mean when I say "one of the hardest parts about designing generic iterators is making it work both for maps and for user-defined types".

[rsc]

Again, there are many issues surrounding iterators that we are not likely to solve in Go 1.18 and should definitely not try to solve in this specific discussion. Let's focus on the other functions.

[earthboundkid]

I think it makes more sense to try out this pattern in just set, see if it's good or bad, and then if it's good, implement it in maps, redo range, etc. Putting in maps first strikes me as rushing it a little too much. If the set API turns out to be wrong, it's only weird package with old-style iterators, instead of two.

[Merovius]

With the retraction of exposing the underlying map of container/set, the most immanent reason for this has disappeared, so I'll retract this for now.

I still think this function is a good idea either way (I wished for it a couple of times in the past), I do still believe it to be my favorite way to solve the iterator-conundrum and I do still believe that it makes sense to start container/set of with a better iteration API.
But for now, I can yield a lost argument :)

@carlmjohnson

I think it makes more sense to try out this pattern in just set

Ironically, I don't particularly like the idea of only having in container/set. It would feel like "magic", without a "blessed" way to get type-safe iterators on maps. Maybe that's irrational though. Either way, if the discussion is about adding it to set, it doesn't belong here (as much as these discussions seem interrelated to me).

[3bodar]

[ Resolved -- leave for later ]

If there should be an EqualFunc counterpart to Equal, shouldn't there also be a CloneFunc counterpart to Clone:

func CloneFunc[K comparable, V1, V2 any](m map[K]V1, transform func(V1) V2) map[K]V2

[deanveloper]

This would essentially just be a Transform function which may be more akin to a stream/iter API.

[ianlancetaylor]

This proposal is aimed to only cover widely used functionality. This one isn't common enough.

[proyb6]

[ Resolved - Filter changed to DeleteIf ]

Other language have .map(), .reduce(), .filter() and often this can seem confusing for newbie when learning in functional paradigm.

I have a preference to choose Collect, Pick or Drop over Filter.

[bcmills]

Prune, maybe?

[bcmills]

Actually, I think this thread substantially overlaps with #47330 (comment).

[tw-ayush]

I believe it will be very valuable to add a function like PutIf(Key, Value) (bool), It'll update only if the key is not present already.

[tw-ayush]

Adding a method to create immutable readonly map replica could be useful, it'll have the same application as passing <- chan to any method. Easier to expose/access data between apis/packages.

[tw-ayush]

Could be as simple as returning an Iterator or returning a map with const set of keys.

[randall77]

[ Resolved -- these are just maps, we don't need to define performance beyond that ]

Same performance note as in sets: #47331 (comment)