Go Commentary #3: Generic Collections, Generics Constraints, AI Bot

Writing generic collection types in Go: the missing documentation

• Context:

  • Generics were released in Go 1.18 (~2y), is not used very much - only in some good cases for methods in slices and maps packages.

• Problem:

  • Wanted to write a sortable Set (slice or map) of any type but the documents for a generic collection are poor and immature.

  type Sortable[T comparable] interface {
      Less(member T) bool
  }
  
  type Name struct {
      First string
      Last string
  }
  
  func (n Name) Less(member Name) bool {
      return n.First < member.First || n.First == member.First && n.Last < member.Last
  }
  
  var _ Sortable[Name] = Name{}
  

  type SortableSet[T Sortable] interface { // cannot use generic type Sortable[T comparable] without instantiation
      Add(member T)
      Size() int
      Contains(member T) bool
      Sorted() []T
  }
  

  • Can try what built-in slices does in slices.go

  func Index[S ~[]E, E comparable](s S, v E) int {
      for i := range s {
          if v == s[i] {
              return i
          }
      }
      return -1
  }
  

  type SortableSet[T Sortable[E], E comparable] interface {
      Add(member T)
      Size() int
      Contains(member T) bool
      Sorted() []T
  }
  

  • But not work for map:

  type MapSet[T Sortable[E], E comparable] struct {
      members map[T]struct{} // invalid map key type T (missing comparable constraint)
  }
  

• Solution:

  // Type set used only for constraints, not vars
  type SortableConstraint[T comparable] interface {
      comparable
      Sortable[T]
  }
  
  type SortableSet[T SortableConstraint[T]] interface {
      Add(member T)
      Size() int
      Contains(member T) bool
      Sorted() []T
  }
  
  type SliceSet[T SortableConstraint[T]] struct {
      members []T
  }
  
  type MapSet[T SortableConstraint[T]] struct {
      members map[T]struct{}
  }
  

• Conclusion:

  • Current Google rearch results are not really helpful since the immaturity

  • The official Go documentations (proposal/ language spec) are too long

  • This article is very handy as considerably pioneering in real life implementation at @Dolt

  • Cheat sheet found in spec by the author:

  type argument      type constraint                // constraint satisfaction
  
  int                interface{ ~int }              // satisfied: int implements interface{ ~int }
  string             comparable                     // satisfied: string implements comparable (string is strictly comparable)
  []byte             comparable                     // not satisfied: slices are not comparable
  any                interface{ comparable; int }   // not satisfied: any does not implement interface{ int }
  any                comparable                     // satisfied: any is comparable and implements the basic interface any
  struct{f any}      comparable                     // satisfied: struct{f any} is comparable and implements the basic interface any
  any                interface{ comparable; m() }   // not satisfied: any does not implement the basic interface interface{ m() }
  interface{ m() }   interface{ comparable; m() }   // satisfied: interface{ m() } is comparable and implements the basic interface interface{ m() }
  
  

Russ Cox is working on a bot

• Context:

  • As there is @gopherbot to try to help automate: labeling, commenting, changing issues’ status…

  • Gaby (Go AI Bot) is being built (experiment) for what LLMs can be used effectively (including identifying what they should not be used for).

  • Source is not official nor open, can help snoop around in this search and help send feedback.

• https://www.dolthub.com/blog/2024-07-01-golang-generic-collections/#the-solution
• https://go.dev/ref/spec
• https://github.com/golang/go/discussions/67901
• https://pkg.go.dev/rsc.io/gaby