Golang 編寫範型集合，官方文檔未提及的訣竅

引言

Go 的泛型功能在 Go 1.18 版本中發佈, 至今已有兩年多了。我們正在使用 Go 開發 Dolt[1] , 這是世界上第一個支持版本控制的 SQL 數據庫。儘管我們有數十萬行 Go 代碼, 但我們並沒有大量使用泛型。我們在一些地方使用泛型 來加速代碼中的高流量部分 [2] , 但總的來說, 除了 slices[3] 和 maps[4] 包中的一些有用的庫方法外, 我們還沒有找到使用泛型的充分理由。

但最近, 我遇到了一個問題, 寫一個泛型集合似乎是一個不錯的解決方案。只有一個問題: 我無法讓它正常工作。我花了幾個小時在一些不太管用的解決方案上打轉。經過令人尷尬的大量試錯、搜索和閱讀之後, 我終於找到了在 Go 中實現泛型集合的正確方法。

由於這個重要用例的搜索結果和文檔都很匱乏, 我想很多嘗試這樣做的人都會犯和我一樣的錯誤, 遇到和我一樣的錯誤。所以我將按照我嘗試的順序來介紹: 兩個錯誤的開始及其症狀, 然後是實際的解決方案。如果你只想看最終解決方案和要點總結, 可以直接跳到那裏。

我們要構建的是什麼: 任意類型的可排序集合

我想創建一個泛型 Set 集合, 它還可以按排序順序返回其內容。我希望使用泛型的類型安全特性, 這意味着不應該需要類型斷言來編寫它。

讓我們先定義一個每個集合成員必須實現的泛型接口, 以及一個具體的集合成員實現。

// Sortable is a generic interface that allows sorting of any type
type Sortable[T any] interface {
    Less(other T) bool
}
// StringSortable implements the Sortable interface for strings
type StringSortable string
func (s StringSortable) Less(other StringSortable) bool {
    return s < other
}

到目前爲止一切順利。我們有一個接口, 可以讓我們對任意實現了 Less()方法的類型的集合內容進行排序。而且 Less方法接受參數化類型, 而不是我們需要進行類型斷言才能進行實際比較的 Sortable接口指針。

這一切看起來很好。現在讓我們定義一個使用 Sortable接口作爲其成員元素的 Set接口。

錯誤開始 #1: 使用兩個泛型類型參數, 複製 slices.Index

我第一次嘗試定義泛型集合接口是這樣的:

type Set[T Sortable] interface {
    Add(item T)
    Remove(item T)
    Contains(item T) bool
    Len() int
    Sorted() []T
}

不幸的是, 它無法編譯, 因爲 Sortable接口本身是泛型的。它需要自己的類型參數。

./set.go:11:10: T (type parameter) is not a type
./set.go:12:15: T (type parameter) is not a type
./set.go:13:18: T (type parameter) is not a type
./set.go:15:13: T (type parameter) is not a type

所以讓我們像這樣添加第二個類型參數:

type Set[T Sortable[E], E any] interface {
    Add(item E)
    Remove(item E)
    Contains(item E) bool
    Len() int
    Sorted() []E
}

這看起來有點奇怪, 但這正是 slices包所做的, 比如下面的 slices.Index函數:

func Index [ S ~[] E , E comparable ]( s S , v E) int

現在讓我們嘗試實現我們的新接口。我們將使用 map 作爲存儲, 因爲它可以爲我們提供集合語義。我的第一次嘗試是這樣的。

type MapSet[T Sortable[E], E any] struct {
    m map[T]struct{}
}
func NewMapSet[T Sortable[E], E any]() *MapSet[T, E] {
    return &MapSet[T, E]{
        m: make(map[T]struct{}),
    }
}

看起來不錯, 但無法編譯:

./set .go:21:7: T does not satisfy comparable

好吧, 既然 map 的鍵需要是可比較的, 我猜我們需要使用可比較的 E類型作爲鍵, 而不是 T類型。

type MapSet[T Sortable[E], E comparable] struct {
    m map[E]struct{}
}
func NewMapSet[T Sortable[E], E comparable]() *MapSet[T, E] {
    return &MapSet[T, E]{
        m: make(map[E]struct{}),
    }
}

這可以編譯了, 太好了! 讓我們完善其餘的方法。哦不, 全是錯誤。

func (s *MapSet[T, E]) Add(item E) {
    s.m[item] = struct{}{}
}
func (s *MapSet[T, E]) Remove(item E) {
    delete(s.m, item)
}
func (s *MapSet[T, E]) Contains(item E) bool {
    _, ok := s.m[item]
    return ok
}
func (s *MapSet[T, E]) Len() int {
    return len(s.m)
}
func (s *MapSet[T, E]) Sorted() []E {
    result := make([]E, 0, len(s.m))
    for k := range s.m {
        result = append(result, k)
    }
    sort.Slice(result, func(i, j int) bool {
        return result[i].Less(result[j])
    })
    return result
}

我可以只做一個類型斷言來修復錯誤嗎? 我不想這樣做, 但也許不可能做得更好。但是不, 這也行不通。

func (s *MapSet[T, E]) Sorted() []E {
    result := make([]E, 0, len(s.m))
    for k := range s.m {
        result = append(result, k)
    }
    sort.Slice(result, func(i, j int) bool {
        return T(result[i]).Less(T(result[j]))
    })
    return result
}

我在這裏卡住了很長時間, 交換對 T和 E的引用, 試圖讓它在所有地方都能編譯。但這個解決方案就是行不通。map 必須以 comparable E爲鍵, 這意味着你無法在 Sortable接口要求的地方返回 Sortable類型。我還嘗試修改 Sortable接口以返回底層的 comparable E, 但這也不是我想要的。回到 drawing board。

這是一個非常準確的翻譯, 我會盡力保持原文的格式和含義。以下是中文翻譯:

錯誤嘗試 #2: 不帶 comparable 的自引用類型定義

事實證明, 使用兩個類型參數 (如 slices 包中的函數) 是一個死衚衕。相反, 我只需要意識到類型定義可以是自引用的, 像這樣:

type Sortable[T any] interface {
    Less(other T) bool
}

這看起來不錯, 但它並不能完全編譯:

type SortableSet[T Sortable[T]] interface {
    Add(T)
    Contains(T) bool
    Len() int
    Sorted() []T
}

讓我們去掉 Sortable 上的 comparable 約束來解決這個問題。

type Sortable[T any] interface {
    Less(other T) bool
}

現在 SortableSet 接口可以正常編譯了。也許我們根本不需要 comparable。接下來是具體的集合類型。這看起來不錯, 但也無法編譯:

type sortableSet[T Sortable[T]] struct {
    m map[T]struct{}
}

這又是同樣的映射鍵問題。由於某種原因, T 不被認爲是有效的鍵, 儘管它是一個接口類型, 而接口總是有效的映射鍵。但這樣可以:

type sortableSet[T Sortable[T]] struct {
    m map[any]struct{}
}

這讓我感覺很奇怪, 但它編譯通過了, 所以我繼續實現。以下是其餘的方法:

func (s *sortableSet[T]) Add(t T) {
    s.m[t] = struct{}{}
}
func (s *sortableSet[T]) Contains(t T) bool {
    _, ok := s.m[t]
    return ok
}
func (s *sortableSet[T]) Len() int {
    return len(s.m)
}
func (s *sortableSet[T]) Sorted() []T {
    result := make([]T, 0, len(s.m))
    for t := range s.m {
        result = append(result, t.(T))
    }
    slices.SortFunc(result, func(a, b T) bool {
        return a.Less(b)
    })
    return result
}

這一切看起來都很棒, 除了 Sorted 方法中的這一行:

result = append(result, t.( T))

這是怎麼回事? 我以爲帶參數化類型的類型斷言不起作用? 但這不僅起作用, 而且是必要的。如果去掉它, 會給我這個非常具體的錯誤消息。

cannot use t ( variable of type any) as T value in argument to append

仔細思考這一點, 它在某種程度上是有道理的: 我們知道 T 被約束爲 Sortable[T], 這意味着這個斷言必須是真的。但由於 Go 是靜態類型的, 當 append 函數的簽名需要 T 時, 我們不能使用 Sortable[T]。它需要類型轉換。

我很高興我終於讓它能工作了, 但我仍然對類型斷言的必要性感到沮喪。一個好的泛型類型系統不應該需要這樣做。我決定再深入研究一下。

更深入的研究: 讓我們嘗試使用切片

也許我只是陷入了與映射鍵相關的一個奇怪的邊緣情況。我確實注意到, 我讀過的所有泛型教程都完全避開了映射, 只關注切片。所以也許用切片會更好?

這裏是一個使用切片進行存儲的 SortableSet 實現。

type sortableSet[T Sortable[T]] struct {
    s []T
}
func (s *sortableSet[T]) Add(t T) {
    if !s.Contains(t) {
        s.s = append(s.s, t)
    }
}
func (s *sortableSet[T]) Contains(t T) bool {
    for _, v := range s.s {
        if v == t {
            return true
        }
    }
    return false
}
func (s *sortableSet[T]) Len() int {
    return len(s.s)
}
func (s *sortableSet[T]) Sorted() []T {
    result := make([]T, len(s.s))
    copy(result, s.s)
    slices.SortFunc(result, func(a, b T) bool {
        return a.Less(b)
    })
    return result
}

又出現了一個錯誤, 這次是在 Contains 方法中。

invalid operation : v == t ( operator == not defined on T)

它抱怨的是這段代碼:

if v == t {

好的, 我可以解決這個問題, 讓我們使用 Less 重新定義我們自己的相等操作: 如果兩個元素都不小於對方, 那麼它們必須相等。

func (s *sortableSet[T]) Contains(t T) bool {
    for _, v := range s.s {
        if !v.Less(t) && !t.Less(v) {
            return true
        }
    }
    return false
}

這按預期工作, 但它讓我感到深深的不安。這裏有些不對勁。要麼是我做錯了什麼而且我不明白, 要麼是 Go 的泛型系統有點問題。長期經驗讓我強烈懷疑前一個結論是正確的。

泛型類型約束的祕密語法

我深深懷疑我無法讓我的代碼工作, 是因爲我表達類型約束的方式。問題是: 我需要一種方法來聲明 Set 中的元素是 Sortable 類型, 同時也是 comparable 的。如果我能弄清楚如何做到這一點, 那麼它將解決兩個問題: 我可以將它們用作映射鍵, 並且 == 將起作用。但是怎麼做呢?

我已經嘗試過在我的 Sortable 接口中添加 comparable 約束, 像這樣:

type Sortable[T comparable] interface {
    Less(other T) bool
}

但當我這樣做時, 任何聲明 Sortable 類型變量的地方都會得到這個錯誤:

interface
 contains type constraints

這個錯誤消息很誘人: 它是否意味着確實存在一個類型約束可以表達這一點?

經過非常堅持不懈的谷歌搜索, 我最終找到了這篇關於 Go 1.20 發佈 [5] 中涉及 comparable 約束的細節的博客。它定義了一個看起來正是我想要的接口: 它將類型約束與普通接口方法聲明結合在一起。

type myInterface interface {
    ~int | ~string
    io.Writer
}

博客解釋了這意味着什麼 (強調是我加的):

這個接口定義了所有底層類型爲 int 或 string 並且也實現了 io.Writer 的 Write 方法的類型集合。

以下是您提供的文本的中文翻譯, 保留了原文的 markdown 格式:

這種泛化的接口不能用作變量類型。但由於它們描述了類型集, 因此被用作類型約束, 即類型集合。

例如, 我們可以編寫一個泛型 min 函數 func min[Pinterface{~int64|~float64}](x,y P)P 它接受任何 int64 或 float64 參數。(當然, 更實際的實現會使用一個枚舉所有帶 < 運算符的基本類型的約束。)

順便說一下, 由於枚舉不帶方法的顯式類型很常見, 一點語法糖允許我們省略包圍的 interface{}, 從而得到更簡潔和慣用的 func min[P~int64|~float64](x,y P)P{…}

這最後一點讓我有點震驚。我讀過的每個教程都使用了後一種語法, 但這兩種形式是等價的。這裏並排展示它們。

func min[P interface{ ~int64 | ~float64 }](x, y P) P
func min[P ~int64 | ~float64](x, y P) P

這是我理解正在發生的事情所需的關鍵洞察: 類型約束被聲明爲接口。慣用版本用語法糖向你隱藏了這一點, 但這就是正在發生的事情。實際上比這更復雜一些: 上面的 interface聲明並不聲明一個類型, 它聲明瞭一個類型集。

博客繼續說:

如果滿足以下條件之一, 類型 T 滿足約束 C:

  • T 實現了 C; 或

  • C 可以寫成 interface{comparable; E} 的形式, 其中 E 是一個基本接口, T 是可比較的並實現了 E。

更多新語法! 其實不是真的新 -- 這是以下內容的內聯形式:

interface {
    comparable
    E
}

;是必需的, 因爲它都在一行上。這是否意味着我可以用同樣的方式定義一個類型約束來解決我的問題? 是的!

解決方案

有了這些知識, 我現在能夠編寫我一直想要的完整的泛型集合解決方案。這個解決方案擁有我想要的一切: 沒有任何類型斷言, 我可以使用泛型類型元素作爲 map 鍵並用 ==比較它們。

type Sortable[T comparable] interface {
    Less(member T) bool
}
type SortableSet[T interface{Sortable[T]; comparable}] interface {
    Add(member T)
    Size() int
    Contains(member T) bool
    Sorted() []T
}
type MapSet[T interface{Sortable[T]; comparable}] struct {
    members map[T]struct{}
}
func NewMapSet[T interface{Sortable[T]; comparable}]() SortableSet[T] {
    return MapSet[T]{
        members: make(map[T]struct{}),
    }
}
type SliceSet[T interface{Sortable[T]; comparable}] struct {
    members []T
}
func NewSliceSet[T interface{Sortable[T]; comparable}]() SortableSet[T] {
    return &SliceSet[T]{
        members: make([]T, 0),
    }
}

我在上面的片段中省略了除類型定義和構造函數之外的所有內容, 但你可以在 這裏 [6] 找到完整的工作實現, 以及一個測試它的 main 方法。

也可以將類型約束聲明爲自己的類型, 如下所示:

type SortableConstraint[T comparable] interface {
    comparable
    Sortable[T]
}

然後你可以在方法簽名中使用該接口名稱, 而不是更冗長的 interface{}語法:

func NewMapSet[T SortableConstraint[T]]() SortableSet[T] {
    return MapSet[T]{
        members: make(map[T]struct{}),
    }
}

是否這樣做可能主要是風格問題, 以及約束需要的頻率, 但我更喜歡這種方式。

也可以在函數聲明中使用多行聲明約束的類型集, 而不使用 ;:

func NewSliceSet[T interface{
    Sortable[T]
    comparable}]() SortableSet[T] {
    return &SliceSet[T]{
        members: make([]T, 0),
    }
}

不過, Go 編譯器對換行符的位置有點挑剔。

要點

以下是你需要理解的關鍵要點, 以便在 Go 中創建自己的泛型集合類型:

我很高興我經歷了這個過程, 因爲它教會了我很多我不知道的關於泛型的知識。這些是 搜索 "Golang generics" 的前 20 個結果 [7] 中完全沒有提到的東西。這有點荒謬, 不是嗎? 定義自己的約束類型不是構建泛型集合類型的基礎嗎, 而泛型集合類型是泛型最突出的用途之一? 我強烈懷疑這些排名靠前的教程都不這樣做, 以及爲什麼它們在示例中避免使用 map 的原因, 是因爲它們無法弄清楚如何使其工作。我理解, 我也做不到!"

您必須仔細閱讀 23,000 字的變更提案 [8] , 才能掌握將內置約束如 comparable與您自己的泛型類型結合使用所需的語法 (而在這 23,000 字中沒有任何使用示例)。或者我猜您也可以閱讀更長的 語言規範 [9] , 但老實說,

我想下次遇到這種情況時, 我就是那種會這麼做的人。規範中實際上有一些非常有用的信息, 在任何教程文章中都沒有提到, 比如這個非常方便的約束滿足示例表:

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() }

真希望我能早點找到它, 並知道我在看什麼。

對我來說, 這裏的真正教訓是: 當某些東西在編程語言中似乎應該是可能的, 但你在任何地方都找不到可用的示例時, 是時候下定決心去閱讀規範了。從長遠來看, 你會節省時間。

結論

嘗試在 Go 中編寫泛型集合類型比應該的更令人沮喪。Google 搜索找不到任何可以借鑑的工作示例, 官方 Go 文檔 (包括泛型提案) 也沒有。希望這篇博客能找到像我一樣迫切需要它的人。

對 Go 泛型有疑問嗎? 或者您對世界上第一個版本控制的 SQL 數據庫感到好奇? 加入我們的 Discord[10] 與我們的工程團隊和其他 Dolt 用戶交流。

參考鏈接

  1. Dolt: https://doltdb.com/
  2. 來加速代碼中的高流量部分: https://www.dolthub.com/blog/2022-04-01-fast-generics/
  3. slices: https://pkg.go.dev/slices
  4. maps: https://pkg.go.dev/maps
  5. Go 1.20 發佈: https://go.dev/blog/comparable
  6. 這裏: https://gist.github.com/zachmu/99e1d4c7701265004cbb898ff395de1f
  7. 搜索 "Golang generics" 的前 20 個結果: https://www.google.com/search?q=golang+generics
  8. 23,000 字的變更提案: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#type-sets
  9. 語言規範: https://go.dev/ref/spec#Typeparameterdeclarations
  10. 加入我們的 Discord: https://discord.gg/gqr7K4VNKe
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/_EczFx3SYYi_Q11udm_hsQ

猜你喜歡