Say you're counting occurrences of keys in a map:
occurrences := make(map[string]int)
As you process keys you increment their corresponding values:
for _, key := range soManyThings() {
occurrences[key]++
}
Now you're tasked with gathering up the N keys with the highest values (in descending order). Before writing any code, imagine that it's still mid-2021 and you're using Go 1.17. Here's what you'd probably come up with:
func TopN(n int, leaderboard map[string]int) []string {
var keys []string
for k := range leaderboard {
keys = append(keys, k)
}
sort.SliceStable(keys, func(i, j int) bool {
return leaderboard[keys[i]] > leaderboard[keys[j]]
})
if n >= len(leaderboard) {
return keys
}
return keys[:n]
}
For loops. If statements. In-place sorting operation. This code is a manifestation of structured programming, which eschews the use of goto statements in order to limit control flow to sequence, selection, and iteration (all of which we see above). Up until pretty recently, this was really the only approach to completing this task in Go. Now we're going to travel forward through time (and Go releases) to gradually rewrite this code in a total different paradigm.
With the release of Go 1.18 came type parameters (AKA 'generics'). It wouldn't be too hard to make our leaderboard type generic such that the 'key' of the map could be any comparable type.
func TopN[K comparable](n int, leaderboard map[K]int) []K {
var keys []K
for k := range leaderboard {
keys = append(keys, k)
}
sort.SliceStable(keys, func(i, j int) bool {
return leaderboard[keys[i]] > leaderboard[keys[j]]
})
if n >= len(leaderboard) {
return keys
}
return keys[:n]
}
Go 1.19 and Go 1.20 were relatively small releases and don't factor into this adventure. Go 1.21 saw the release of a few new built-in functions, and we can use min to simplify the final return:
func TopN[K comparable](n int, leaderboard map[K]int) []K {
var keys []K
for k := range leaderboard {
keys = append(keys, k)
}
sort.SliceStable(keys, func(i, j int) bool {
return leaderboard[keys[i]] > leaderboard[keys[j]]
})
return keys[:min(n, len(leaderboard))]
}
Go 1.21 also introduced five new standard library packages! Of specific interest to us are "cmp", "maps", and "slices".
"cmp"
The new "cmp" package defines the type constraint Ordered and two new generic functions
LessandComparethat are useful with ordered types.
Useful for what? Well, sorting, of course! Note that the callback func passed to sort.SliceStable above is similar in character to cmp.Less.
"maps" and "slices"
The new
"slices"package provides many common operations on slices, using generic functions that work with slices of any element type.The new
"maps"package provides several common operations on maps, using generic functions that work with maps of any key or element type.
Unfortunately, much of the API initially implemented at golang.org/x/exp/maps (like the Keys func) as well as golang.org/x/exp/slices allocated (potentially large) slices so the Go maintainers opted to omit those functions in the standard library until the release of iterators ...
Go 1.23 is our final stop on our journey, where "range-over-func iterators" were officially released, along with the aforementioned functions in the "slices" and "maps" packages. The new maps.Keys(...) function returns an iterator the supplies the keys of a map. The slices.SortedStableFunc(...) function receives an iterator as well as a comparison function (like cmp.Compare!) and returns a sorted slice. Perfect!
func TopN(n int, leaderboard map[string]int) []string {
keys := maps.Keys(leaderboard)
ranked := slices.SortedStableFunc(keys, func(i, j string) int {
return -cmp.Compare(leaderboard[i], leaderboard[j])
})
return ranked[:min(n, len(leaderboard))]
}
So, rather than a greater-than operator (>) in a 'less func', we now negate the result of cmp.Compare to achieve keys sorted in descending order.
Less than half as long, the above solution has the same elements as the first, but its character is pretty different. There is no mutable state visible in this code. We are approaching a functional paradigm.
But the callback function passed to slices.SortedStableFunc still sticks out a bit, and I wish we could extract it to a separate function, but it is a closure around the leaderboard map (local state) and so that's not an option. But what if we made the leaderboard its own map type? That would allow us to define TopN as a method of the new type, rather than as a package-level function. This would allow us to extract a method to serve as the comparison func.
Also, we can make the map value any type that satisfies cmp.Ordered for maximum usability.
type Leaderboard[K comparable, V cmp.Ordered] map[K]V
func (this Leaderboard[K, V]) TopN(n int) []K {
return slices.SortedStableFunc(maps.Keys(this),
this.compare)[:min(n, len(this))]
}
func (this Leaderboard[K, V]) compare(i, j K) int {
return -cmp.Compare(this[i], this[j])
}
And there you have it! I'm actually still amazed that we really can approach a more concise, 'functional' style in Go nowadays--it's like a whole new language! We ended up with less code, but nearly every line uses one of the relatively new features we discussed.
It's a great time to be a Gopher!
Reference Tests:
import (
"testing"
"github.com/mdw-go/testing/v2/assert"
"github.com/mdw-go/testing/v2/should"
)
func TestLeaderboard(t *testing.T) {
leaderboard := Leaderboard[string, int]{
"a": 2,
"b": 3,
"c": 1,
"d": 4,
}
assert.So(t, leaderboard.TopN(3),
should.Equal, []string{
"d",
"b",
"a",
},
)
assert.So(t, leaderboard.TopN(5),
should.Equal, []string{
"d",
"b",
"a",
"c",
},
)
}
Aside: a truly functional implementation
Now, not to spoil Go's fun, but the Clojure implementation is quite lovely:
user=> (defn top-n [n leaderboard]
(->> leaderboard
(sort-by val >)
(map first)
(take n)))
user=> (top-n 3 {:a 2 :b 3 :c 1 :d 4})
(:d :b :a)
Incredibly concise, yet still very readable. Clojure's nice like that.