1
\$\begingroup\$

Yesterday I build some generic functions for the new official Golang 1.18 release. What do you think about it and what could be added and improved?

package main

import (
    "fmt"
    "log"
    "reflect"
)

func ToString(this any) string {
    return fmt.Sprintf("%v", this)
}

type List[V any] []V

func (this List[V]) Size() int {
    return len(this)
}
func (this *List[V]) Add(next V) *List[V] {
    *this = append(*this, next)
    return this
}
func (this List[V]) Get(v int) V {
    return this[v]
}
func (this *List[V]) Map(f func(V) V) *List[V] {
    var res List[V]
    for _, v := range *this {
        res.Add(f(v))
    }
    return &res
}
func (this *List[V]) Filter(f func(V) bool) *List[V] {
    var res List[V]
    for _, v := range *this {
        if f(v) {
            res.Add(v)
        }
    }
    return &res
}

type Map[K comparable, V any] map[K]V

func (this Map[K, V]) Size() int {
    return len(this)
}

func (this *Map[K, V]) Add(key K, value V) *Map[K, V] {
    (*this)[key] = value
    return this
}

func (this *Map[K, V]) Get(key K) V {
    return (*this)[key]
}

func (this Map[K, V]) Keys() *List[V] {
    res := make(List[V], 0, len(this))
    for _, v := range this {
        res = append(res, v)
    }
    return &res
}

func (this Map[K, V]) Values() *List[V] {
    res := make(List[V], 0, len(this))
    for _, v := range this {
        res = append(res, v)
    }
    return &res
}

func (this *Map[K, V]) ContainsKey(key K) bool {
    if _, ok := (*this)[key]; ok {
        return true
    }
    return false
}

func (this *Map[K, V]) ContainsValue(value V) bool {
    for _, v := range *this {
        if reflect.TypeOf(v) == reflect.TypeOf(value) && ToString(v) == ToString(value) {
            return true
        }
    }
    return false
}

func (this *Map[K, V]) Map(f func(K, V) (K, V)) *Map[K, V] {
    res := make(Map[K, V], 0)
    for k, v := range *this {
        res.Add(f(k, v))
    }
    return &res
}

func (this *Map[K, V]) Filter(f func(V) bool) *Map[K, V] {
    res := make(Map[K, V], 0)
    for k, v := range *this {
        if f(v) {
            res.Add(k, v)
        }
    }
    return &res
}

func main() {
    listTemp := make(List[int], 0)
    listTemp.Add(1)
    log.Println(listTemp)
    log.Println("string: " + ToString(listTemp.Get(0)))

    mapTemp := make(Map[string, string], 0)
    mapTemp.Add("al", "aluminum").Map(func(k string, v string) (string, string) {
        log.Println("first call: " + v)
        if v == "aluminum" {
            return k, "aluminium"
        }
        return k, v
    }).Values().Add("silver").Map(func(v string) string {
        log.Println("second call: " + v)
        return v
    })

    mapTemp.Add("ag", "silver")
    mapTemp.Add("o", "oxygen")

    log.Println(mapTemp)
    log.Println("string: " + ToString(mapTemp))
    log.Println(mapTemp.ContainsKey("al"))
    log.Println(mapTemp.ContainsKey("1"))
    log.Println(mapTemp.Values())
    log.Println(mapTemp.Size())
    log.Println(mapTemp.Values().Size())
    log.Println(mapTemp.Get("al"))
    log.Println(mapTemp.Values().Get(2))

    mapTemp2 := make(Map[string, int], 0)
    log.Println(mapTemp2.Add("al", 1).ContainsValue(1))
}

You can also try it out on golang playground: https://go.dev/play/p/7OFh0KCmHSc

I wanted to build functions which you can add behind each other like in Java or Dart, therefore I give often give back the value given into the function or for example on Map() I give back the changed value. Is this intuitive?

I didn't find any functioning solutions out there yet, so please feel free to use my solution and improve it.

Edit: After a bit of time I would also add these functions:

func (l *List[V]) RemoveFirst() *List[V] {
    if l.Size() > 0 {
        res := (*l)[1:]
        return &res
    }
    return l
}

func (l *List[V]) RemoveLast() *List[V] {
    if l.Size() > 0 {
        res := (*l)[:len(*l)-1]
        return &res
    }
    return l
}

(...)

func (m *Map[K, V]) RemoveKey(k K) *Map[K, V] {
    res := *m
    delete(res, k)
    return &res
}

Instead of this I now changed to a single character as a receiver (l for list and m for map).

Do you think that it would make sense to also change the initial map and list or is it more intuitive to just give back the changed value? So if you call list.RemoveKey(key) alter the initial list AND give back the altered value or ONLY give back the altered value?

\$\endgroup\$
3
  • \$\begingroup\$ Please don't call your receiver this. Generally, the receiver is a single character variable, so instead of func (this T) Foo(), write func (t T) Foo() \$\endgroup\$ Apr 5 at 9:21
  • \$\begingroup\$ I think you're right, especially because this is a generic name for a lot of languages, so it's probably good practice to not use this at all? \$\endgroup\$
    – Erik Bent
    Apr 5 at 12:28
  • \$\begingroup\$ It's part of the code review comments (a coding style document/guideline) you can find it here. It actually mentions the use of this, and how you shouldn't use it. Generally speaking receivers and argument variables are short, often a single character, as you can see throughout the standard library \$\endgroup\$ Apr 5 at 14:22

1 Answer 1

1
\$\begingroup\$

Right, I've had a closer look at the Map type you posted here (don't know why, but that one piqued my interest more than the list). There's quite a lot to unpack already, so I'm just going to focus on that part of your code to start things off with. After that, I've added a couple of notes specifically on the List type, but there's not much to say about your List specifically, so the bulk of this review focuses on the Map type (as a lot of the comments apply to List, too), and your use of generics specifically.

Full disclosure: I'm not opposed to generics in general, but I've seen progress on projects crawl to a halt one too many times because of generic-overuse. Generics are a powerful tool, but shouldn't be used for the sake of using them. They should be used when called for. Golang generics has been talked of for years and years now, and I've always been of the opinion that I'd need to find myself in a situation where generics would actually boost productivity for me to want them. This has happened, but really, it hasn't happened anywhere near as often as you'd expect given how many people have claimed that "without generics, the language is useless".
Take this as you will, but I'm just telling you that I may have some bias going in to this, but I've tried to ignore the "why" you wrote this, and instead focused on what you wrote.


Let's start with some basic comments about the generic map, and how you're using it.

type Map[K comparable, V any] map[K]V

That's fine: you're essentially creating a type that can be instantiated to be any sort of map. Shocker, I know, that's what generics are supposed to do. What is important to note is that underneath it all, your type is just a map, that has the types for K and V set at compile-time. To all intents and purposes, then, its usage is no different to that of any other map.

First of all, this is a bit of a pedantic nit-pick thing, but this:

mapTemp := make(Map[string, string], 0)

can be written like you would do any other map (with some generic syntax):

mapTemp := Map[string, string]{}

This also allows you to create generic map literals:

mapTemp := Map[int64, uint64]{
    1: 1,
    2: 2,
}

That's nice, and I thought I'd mention it here because your code looks like you hadn't considered this.

Another thing to consider is that, because this is just a map like any other, there's no reason why somebody wouldn't be able to write this:

mapTemp["foo"] = "bar"
// and
delete(mapTemp, "foo")

Completely side-stepping your methods.

Putting it bluntly, that's what I would do, because I'm kind of struggling to see why I'd use those methods like this:

func (m *Map[K, V]) RemoveKey(k K) *Map[K, V] {
    res := *m
    delete(res, k)
    return &res
}

Looking at this method, you may think that you're deleting a key from a copy (res := *m), and then returning a copy of the map. The thing is: both m and res end up pointing to the same underlying map. The use of res is redundant at best, and misleading at worst. Remember how go maps are implemented underneath:

type hmap struct {
    Count int // number of data stored in map, used by Len (map)
    Flags uint8 // flags will identify the current map. For example, the 4th bit of hashwriting = 4 indicates that goroutine is writing to the map
    B uint8 // map has 2 ^ B buckets
    Hash 0 uint32 // seed of hash algorithm

    Buckets unsafe. Pointer // 2 ^ B arrays of buckets
    Oldbuckets unsafe. Pointer // during the expansion, there is a value in oldbuckets. Map is incremental expansion, not one-time completion. Expansion is mainly triggered by insertion and deletion
    ......
}

As you can see, the actual data is accessed/managed through unsafe.Pointer fields (i.e. pointers). Creating a copy is just going to copy the exact same pointers over, so delete(res, k) will delete from m, too.

That brings me to the biggest gripe I have with all of your methods: Why use pointer receivers in the first place?

func (m Map[K, V]) Add(k K, v V) {
    m[k] = v
}

works just as well. Sure, you don't have the chainable interface you have now, but let's be honest: do you care? In reality, you don't really see all that much code that does something like this:

aMap["foo"] = 1
aMap["bar"] = 2
aMap["zar"] = 3

You more often see keys being copied over in a loop, in which case a chainable interface doesn't help, or you see maps being initialised with a set of K/V pairs. As I mentioned earlier, you can do this with your generic map types all the same, and without messy code like:

tempMap.Add("foo", 1).Add("bar", 2).Add("zar", 3)

Basically, if I were to implement a generic map type like this (with convenience methods like Filter and Keys - which we'll cover later), I'd just change the pointer receivers to be regular receivers, and I would preserve certain behaviours that you're currently missing (mainly the bool return when getting something from a map that allows you to differentiate between a nil value and a missing key):

func (m Map[K, V]) Set(k K, v V) {
    m[k] = v
}
func (m Map[K, V]) Get(k K) (V, bool) {
    v, ok := m[k]
    return v, ok
}

Other than that, your generic maps are fine, but they don't really offer any advantages over conventional maps. They're definitely not safe for concurrent access, for a start. I'd consider wrapping this map in a type that adds a mutex or something to at least provide that safety, and have a compelling reason to force people to use this interface.

If not, the methods you've added like Filter are more of a nuisance than they offer a real advantage. As they stand, I can't use them in existing code:

myMap := map[string]string{}
myMap.Filter() // doesn't exist

To use this Filter method, I have to go through my code and change myMap := pkg.Map[string, string]{}, then update all functions that I call with this map as an argument. It's a massive PITA to refactor things this way.

Even if you bite this bullet, there will be a time where you have to pass a regular map to some 3rd party package, so you'll probably want to add some utility function like this:

func (m Map[K, V]) Raw() map[K]V {
    ret := make(map[K]V, len(m))
    for k, v := range m {
        ret[k] = v
    }
    return ret
}

But this comes at a cost: every time you call this, you'll allocate a copy of the map, for no reason other than, what IMO would be, your insistence on using a generic type, rather than relying on generic functions to achieve exactly the same thing...

That would be my main argument to get rid of the methods/receiver functions. Instead, I would much rather rewrite the Filter function into something like this:

func Filter[K comparable, V any](m map[K]V, f func(V) bool) map[K]V {
    ret := make(map[K]V, len(m))
    for k, v := range m {
        if f(v) {
            ret[k] = v
        }
    }
    return ret
}

Now I have a generic function that allows me to filter all existing maps through this single function. If you already have this generic map type in use, you can easily adapt this Filter function to work with both:

func Filter[K comparable, V any, M ~map[K]V](m M, f func(V) bool) M {
    ret := make(M, len(m))
    for k, v := range m {
        if f(v) {
            ret[k] = v
        }
    }
    return ret
}

There we go: filter generic maps, and existing ones in a single function. You can do the same thing with the other methods just as easily. You want a function to get the keys from any map? Easy:

func Keys[K comparable, V any, M ~map[K]V](m M) []K {
    ret := make([]K, 0, len(m))
    for k := range m {
        ret = append(ret, k)
    }
    return ret
}

Map Recap

Just to summarise:

  1. The generic type itself is fine, but limits you to new code that uses this map type, or requires a rewrite of existing code. That's sub-optimal. If you adopt this type, which just will leave you having to copy the data into an actual map just to use some package that you can't convert.
  2. Having a generic way to Filter a map, or get the keys is a valid use-case for generics, but doesn't merit creating a new type. Generic functions can be written to work with any type that, at its core, is just a map. These functions are even more generic because they're not tied to a specific type.
  3. A type like this Map that aims to supersede an existing one should not take away any of the existing features (e.g v, ok := m[k] boolean flag). It should also have a reason for existing (ie add something of value). I can't really see a reason for this map to exist if it doesn't have some intrinsic feature that a regular map doesn't have (thread-safety for example).

I'm going to end the Map review here, and I'll revisit this once my fingers have recovered from typing this wall of text and review the List type. I suspect, however, that much of what I've said about the Map type will carry over to the List type, as it seems to be equivalent to []any, but instead of allowing s = append(s, 1, 2, 3, 4) (variadic append), you've restricted the interface to s.Add(1).Add(2).Add(3), which is so cumbersome, most people will just end up using append directly and again: side-step the methods you wrote.


Well, I just couldn't help myself and briefly looked at the implementation of List. As I expected, it's basically just a slice, masked by some generic syntax. In doing so, you've limited the possibility to append multiple values in a single line (the append comment I made earlier), to gain very little...

Sure, you can now have a variable of type List[int] or something, and call list.Filter() on it, but by slightly altering your Filter function, you can open the same Filter function open to all slices in existing code:

func Filter[V any](s []V, func (v V) bool) []V {
    ret := make([]V, 0, len(s))
    for _, v := range s {
        if f(v) {
            ret = append(ret, v)
        }
    }
    return ret
}

One thing that really stands out, though, is the Map function. I don't see why you'd create a copy of the original slice/list there. When I map a slice, I kind of expect that to alter the slice I'm mapping, so a generic MapSlice function for me would look something like this:

func MapSlice[V any](s []V, f func(V) V) {
    for i, v := range s {
        s[i] = f(v)
    }
}

If I don't want to alter the original slice, I would just call it like this:

 MapSlice(append([]int{}, s...), func(i int) int { return i+1 })

When it comes to the remove first/last functions you want to add, I can only say: what's the use? The native slice/map types are arguably better to use, and if you want to remove the first or last element from a slice, you can do that in-line, or at worst have a function like

func RMFirst[V any](s []V) []V {
    if len(s) == 0 {
        return s
    }
    return s[1:]
}

Deleting keys from maps, because delete(m, k) where k doesn't exist is defined as a no-op, doesn't merit a function - generic or otherwise.

The main reason why I didn't review the List code along side the Map stuff was that I expected the List type to be more than a masked slice. When I talk about lists, I'm thinking back to the old C/C++ days and my mind goes to single/double linked lists and the like. None of the methods you have here, though, suggest that this is a list. You just have a slice, and nothing more.

Like I said earlier: if you're going to introduce a new type, don't remove existing features (e.g. append), and add new ones: linking in the list, list iterators, and thread safety. Again, doing so would likely require you to create a struct, add a mutex, add a node type to link your list, and requires custom code to insert/delete values. and all that good stuff.


As a bit of an insomniac, I found myself writing a little bit of code last night and decided to implement some kind of thread-save generic map-based type. I decided to add a method to easily merge in an existing map, and extract a regular old map from the wrapper type. I also thought that, if thread safety is a concern (which is why you'd use a type like sync.Map), I figured it makes sense to have an iterator of sorts. The iterator itself would not be safe for concurrent use, but then the rationale is that you would spawn a number of routines and each one of them would receive their own iterator, so that's not a major issue. I wrote this in pretty much one go, and added some tests to make sure everything works as expected. The package itself looks something like this:

import (
    "errors"
    "sort"
    "sync"
)

type SMap[K comparable, V any] struct {
    mu *sync.RWMutex
    m  map[K]V
}

type SMapIter[K comparable, V any] struct {
    l    sync.Locker
    i    int
    keys []K
    k    K
    v    V
    m    *SMap[K, V]
}

// NewSMap creates a new sync-safe map
func NewSMap[K comparable, V any](init map[K]V) *SMap[K, V] {
    r := &SMap[K, V]{
        mu: &sync.RWMutex{},
        m:  map[K]V{},
    }
    // initialise
    r.Merge(init, true) // overwrite doesn't make a difference but we can skip pointless lookups
    return r
}

// Len returns underlying map length
func (s *SMap[K, V]) Len() int {
    s.mu.RLock()
    defer s.mu.RUnlock()
    return len(s.m)
}

// Merge merges a given map into this type
func (s *SMap[K, V]) Merge(m map[K]V, overwrite bool) {
    if len(m) == 0 {
        return
    }
    s.mu.Lock()
    for k, v := range m {
        if !overwrite {
            if _, ok := s.m[k]; ok {
                continue
            }
        }
        s.m[k] = v
    }
    s.mu.Unlock()
}

// Clone creates a copy
func (s *SMap[K, V]) Clone() *SMap[K, V] {
    s.mu.RLock()
    r := NewSMap[K, V](s.m) // create new instance
    s.mu.RUnlock()
    return r
}

// Get simply gets the value for a given key, returns false if the key doesn't exist
func (s *SMap[K, V]) Get(k K) (V, bool) {
    s.mu.RLock()
    v, ok := s.m[k]
    s.mu.RUnlock()
    return v, ok
}

// Set sets a value for a given key (overwrites existing value)
func (s *SMap[K, V]) Set(k K, v V) {
    s.mu.Lock()
    s.m[k] = v
    s.mu.Unlock()
}

// CAS is a simple Check And Set, returns false if the key was not set
func (s *SMap[K, V]) CAS(k K, v V) bool {
    s.mu.Lock()
    defer s.mu.Unlock()
    if _, ok := s.m[k]; ok {
        return false
    }
    s.m[k] = v
    return true
}

// Raw returns a copy of the underlying map as a standard map[K]V
func (s *SMap[K, V]) Raw() map[K]V {
    s.mu.RLock()
    ret := make(map[K]V, len(s.m))
    for k, v := range s.m {
        ret[k] = v
    }
    s.mu.RUnlock()
    return ret
}

// Delete deletes one or more of the keys. Non-existing keys are a no-op as with a normal map
func (s *SMap[K, V]) Delete(keys ...K) {
    s.mu.Lock()
    for _, k := range keys {
        delete(s.m, k)
    }
    s.mu.Unlock()
}

// Keys returns a slice of all keys
func (s *SMap[K, V]) Keys() []K {
    s.mu.RLock()
    ks := make([]K, 0, len(s.m))
    for k := range s.m {
        ks = append(ks, k)
    }
    s.mu.RUnlock()
    return ks
}

// Iter returns an iterator, iteration is non-deterministic like a normal map, unless
// the optional sort function is provided, in which case the keys will be sorted using sort.SliceStable
// After iterating over the values, Close must be called!
func (s *SMap[K, V]) Iter(f func(a, b int) bool) *SMapIter[K, V] {
    iter := &SMapIter[K, V]{
        l: s.mu.RLocker(),
        m: s,
        i: 0,
    }
    iter.l.Lock() // acquire lock already
    keys := s.Keys()
    if f != nil {
        sort.SliceStable(keys, func(i, j int) bool {
            return f(keys[i], keys[j])
        })
    }
    iter.keys = keys
    return iter
}

// Next moves the iterator to the next element in the map, returns false if we already reached the end
func (i *SMapIter[K, V]) Next() bool {
    if i.i >= len(i.keys) {
        return false
    }
    // set key/value
    i.k = i.keys[i.i]
    i.v = i.m.m[i.k]
    i.i++ // move index
    return true
}

// Key returns current key
func (i *SMapIter[K, V]) Key() (K, error) {
    var k K
    if i.keys == nil {
        return k, errors.New("iterator closed")
    }
    return i.k, nil
}

// Val returns current value
func (i *SMapIter[K, V]) Val() (V, error) {
    var v V
    if i.keys == nil {
        return v, errors.New("iterator closed")
    }
    return i.v, nil
}

// Close releases the iterator
func (i *SMapIter[K, V]) Close() {
    var (
        k K
        v V
    )
    // clear all fields
    i.keys = nil
    i.k = k
    i.v = v
    i.i = 0
    i.m = nil
    // release lock
    i.l.Unlock()
}

I've since created a repo on github in case anyone is interested.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.