函數式編程在 Go 泛型下的實用性探索

我是一隻可愛的土撥鼠,專注於分享 Go 職場、招聘和求職,解 Gopher 之憂!歡迎關注我。

歡迎大家加入 Go 招聘交流羣,來這裏找志同道合的小夥伴!跟土撥鼠們一起交流學習。

背景

函數式編程(Functional Programming / FP)作爲一種編程範式,具有無狀態、無副作用、併發友好、抽象程度高等優點。目前流行的編程語言(C++、Python、Rust)都或多或少地引入了函數式特性,但在同作爲流行語言的 Golang 中卻少有討論。

究其原因,大部分的抱怨 Golang 函數式編程簡述 [1] 、GopherCon 2020: Dylan Meeus - Functional Programming with Go[2] 集中於 Go 缺乏對泛型的支持,難以寫出類型間通用的函數。代碼生成只能解決一部分已知類型的處理,且無法應對類型組合導致複雜度(比如實現一個通用的 TypeA → TypeB 的 map 函數)。

有關泛型的提案 spec: add generic programming using type parameters #43651[3] 已經被 Go 團隊接受,並計劃在 2022 年初發布支持泛型的 Go 1.18,現在 golang/go 倉庫的 master 分支已經支持泛型。

This design has been proposed and accepted as a future language change. We currently expect that this change will be available in the Go 1.18 release in early 2022. Type Parameters Proposal[4]

基於這個重大特性,我們有理由重新看看,函數式特性在 Go 泛型的加持下,能否變得比以往更加實用。

概述

這篇文章裏,我們會嘗試用 Go 的泛型循序漸進地實現一些常見的函數式特性,從而探索 Go 泛型的優勢和不足。

除非額外說明(例如註釋中的 // INVALID CODE!!!),文章裏的代碼都是可以運行的(爲了縮減篇幅,部分刪去了 package main 聲明和 main 函數,請自行添加)。你可以自行 從源碼編譯 [5] 一個 master 版本的 go 來提前體驗 Go 的泛型,或者用 The go2go Playground[6] 提供的在線編譯器運行單個文件。

泛型語法

提案的 #Very high level overview[7] 一節中描述了爲泛型而添加的新語法,這裏簡單描述一下閱讀本文所需要的語法:

提示

「基礎類型」在提案中爲 “underlying type”,目前尚無權威翻譯,在本文中使用僅爲方便描述。

高階函數

在函數式編程語言中,📖 高階函數 [8] (Higher-order function)是一個重要的特性。高階函數是至少滿足下列一個條件的函數:

Golang 支持閉包,所以實現高階函數毫無問題:

func foo(bar func() string) func() string {
        return func() string {
                return "foo" + " " + bar()
        }
}

func main() {
        bar := func() string {
                return "bar"
        }
        foobar := foo(bar)
        fmt.Println(foobar())
}
// Output:
// foo bar

filter 操作是高階函數的經典應用,它接受一個函數 f(func (T) bool)和一個線性表 l([] T),對 l 中的每個元素應用函數 f,如結果爲 true,則將該元素加入新的線性表裏,否則丟棄該元素,最後返回新的線性表。

根據上面的泛型語法,我們可以很容易地寫出一個簡單的 filter 函數:

func Filter[T any](f func("T any") bool, src []T) []{
        var dst []T
        for _, v := range src {
                if f(v) {
                        dst = append(dst, v)
                }
        }
        return dst
}

func main() {
        src := []int{-2, -1, -0, 1, 2}
        dst := Filter(func(v int) bool { return v >= 0 }, src)
        fmt.Println(dst)
}
// Output:
// [0 1 2]

代碼生成之困

在 1.17 或者更早前的 Go 版本中,要實現通用的 Filter 函數有兩種方式:

  1. 使用 interface{} 配合反射,犧牲一定程度的類型安全和運行效率

  2. 爲不同數據類型實現不同的 Filter 變種,例如 FilterIntFilterString 等,缺點在於冗餘度高,維護難度大

方式 2 的缺點可以通過代碼生成規避,具體來說就使用相同的一份模版,以數據類型爲變量生成不同的實現。我們在 Golang 內部可以看到不少 代碼生成的例子 [9] 。

那麼,有了代碼生成,我們是不是就不需要泛型了呢?

答案是否定的:

  1. 代碼生成只能針對已知的類型生成代碼,明明這份模版對 float64 也有效,但作者只生成了處理 int 的版本,我們作爲用戶無能爲力(用 interface{} 同理,我們能使用什麼類型,取決於作者列出了多少個 type switch 的 cases)

    而在泛型裏,新的類型約束語法可以統一地處理「基礎類型」相同的所有類型:

    type signed interface {
            ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~float32 | ~float64 | ~complex64 | ~complex128
    }
        
    func Neg[T signed](n T "T signed") T {
            return -n
    }
        
    func main() {
            type MyInt int
        
            fmt.Println(Neg(1))
            fmt.Println(Neg(1.1))
            fmt.Println(Neg(MyInt(1)))
    }
    // Output:
    // -1
    // -1.1
    // -1
  2. 代碼生成難以應對需要類型組合的場景,我們來看另一個高階函數 map:接受一個函數 f(func (T1) T2)和一個線性表 l1([]T1),對 l1 中的每個元素應用函數 f,返回的結果組成新的線性表 l2([]T2

    如果使用代碼生成的話,爲了避免命名衝突,我們不得不寫出 MapIntIntMapIntUintMapIntString 這樣的奇怪名字,而且由於類型的組合,代碼生成的量將大大膨脹。

    我們可以發現在現有的支持 FP 特性的 Go library 裏:

    如果使用泛型的話,只需要定義這樣的簽名就好了:

    func Map[T1, T2 any](f func(T1 "T1, T2 any") T2, src []T1) []T2

無糖的泛型

Go 的語法在一衆的編程語言裏絕對算不上簡潔優雅。在官網上看到操作 channel 時 <- 的直觀便捷讓你心下暗喜,而一旦你開始寫 real world 的代碼,這個語言就處處難掩設計上的簡陋。泛型即將到來,而這個語言的其他部分似乎沒有做好準備:

閉包語法

在 Haskell 中的匿名函數形式非常簡潔:

filter (\x -> x >= 0) [-2, -1, 0, 1, 2]
-- Output:
-- [0,1,2]

而在 Golang 裏,函數的類型簽名不可省略,無論高階函數要求何種簽名,調用者在構造閉包的時候總是要完完整整地將其照抄一遍 Golang 函數式編程簡述 [13]

func foo(bar func(a int, b float64, c string) string) func() string {
        return func() string {
                return bar(1, 1.0, "")
        }
}

func main() {
        foobar := foo(func(_ int, _ float64, c string) string {
                return c
        })
        foobar()
}

這個問題可以歸結於 Go 團隊爲了保持所謂的「大道至簡」,而對類型推導這樣提升效率降低冗餘的特性的忽視(泛型的姍姍來遲又何嘗不是如此呢?)。proposal: Go 2: Lightweight anonymous function syntax #21498[14] 提出了一個簡化閉包調用語法的提案,但即使該提案被 accept,我們最快也只能在 Go 2 裏見到它了。

方法類型參數

鏈式調用 [15] (Method chaining)是一種調用函數的語法,每個調用都會返回一個對象,緊接着又可以調用該對象關聯的方法,該方法同樣也返回一個對象。鏈式調用能顯著地消除調用的嵌套,可讀性好。我們熟悉的 GORM 的 API 裏就大量使用了鏈式調用:

db.Where("name = ?""jinzhu").Where("age = ?", 18).First(&user)

在函數式編程中,每個高階函數往往只實現了簡單的功能,通過它們的組合實現複雜的數據操縱。

在無法使用鏈式調用的情況下,高階函數的互相組合是這樣子的(這僅僅是兩層的嵌套):

Map(func(v int) int { return v + 1 },
   Filter(func(v int) bool { return v >= 0 },
      []int{-2, -1, -0, 1, 2}))

如果用鏈式調用呢?我們繼續沿用前面的 filter ,改成以下形式:

type List[T any] []T

func (l List[T]) Filter(f func(T) bool) List[T] {
        var dst []T
        for _, v := range l {
                if f(v) {
                        dst = append(dst, v)
                }
        }
        return List[T](dst "T")
}

func main() {
        l := List[int]([]int{-2, -1, -0, 1, 2} "int").
                Filter(func(v int) bool { return v >= 0 }).
                Filter(func(v int) bool { return v < 2 })
        fmt.Println(l)
}
// Output:
// [0 1]

看起來很美好,但爲什麼不用 map 操作舉例呢?我們很容易寫出這樣的方法簽名:

// INVALID CODE!!!
func (l List[T1]) Map[T2 any](f func(T1 "T1]) Map[T2 any") T2) List[T2]

很遺憾這樣的代碼是沒法通過編譯的,我們會獲得以下錯誤:

invalid AST: method must have no type parameter

提案的 #No parameterized methods[16] 一節明確表示了方法(method,也就是有 recevier 的函數)不支持單獨指定類型參數:

This design does not permit methods to declare type parameters that are specific to the method. The receiver may have type parameters, but the method may not add any type parameters. 1[17]

這個決定實際上是個不得已的妥協。假設我們實現了上述的方法,就意味對於一個已經實例化了的 List[T] 對象(比如說 List[int]),它的 Map 方法可能有多個版本:Map(func (int) int) List[int] 或者 Map(func (int) string) List[string],當用戶的代碼調用它們時,它們的代碼必然在之前的某個時刻生成了,那麼應該在什麼時候呢?

  1. 在編譯期,更準確地說,在編譯的 link 階段,這需要 linker 去遍歷整個 call graph,確定程序中到底使用了幾個版本的 Map。問題在於反射(reflection)的存在:用戶可以用 reflect.MethodByName 動態地調用對象的方法,所以即使遍歷了整個 call graph,我們也無法確保用戶的代碼到底調用了幾個版本的 Map

  2. 在運行期,在第一次調用方法時 yield 到 runtime 中,生成對應版本的函數後 resume 回去,這要求 runtime 支持 JIT(Just-in-time compilation),而目前 Go 並不支持,即使未來 JIT 的支持提上日程,這也不是一蹴而就的事情

綜上,Go 團隊選擇了不支持給 method 指定類型參數,完美瞭解決這個問題 🎉。

惰性求值

📖 惰性求值 [18] (Lazy Evaluation)是另一個重要的函數式特性,一個不嚴謹的描述是:在定義運算時候,計算不會發生,直到我們需要這個值的時候才進行。其優點在於能使計算在空間複雜度上得到極大的優化。

下面的代碼展示了一個平平無奇的 Add 函數和它的 Lazy 版本,後者在給出加數的時候不會立刻計算,而是返回一個閉包:

func Add(a, b int) int {
        return a + b
}

func LazyAdd(a, b int) func() int {
        return func () int {
                return a + b
        }
}

上面這個例子沒有體現出惰性求值節省空間的優點。基於我們之前實現的高階函數,做以下的運算:

l := []int{-2, -1, -0, 1, 2}
l = Filter(func(v int) bool { return v > -2 }, l)
l = Filter(func(v int) bool { return v < 2 }, l)
l = Filter(func(v int) bool { return v != 0 }, l)
fmt.Println(l)

計算過程中會產生 3 個新的長度爲 5 的 []int,空間複雜度爲 O(3∗N),儘管常數在複雜度分析時經常被省略,但在程序實際運行的時候,這裏的 3 就意味着 3 倍的內存佔用。

假設這些高階函數的求值是惰性的,則計算只會在對 fmt.Println 對參數求值的時候發生,元素從原始的 l 中被取出,判斷 if v > -2if v < 2,最後執行 v + 1,放入新的 []int 中,空間複雜度依然是 O(N),但毫無疑問地我們只使用了一個 `[]int``。

泛型的引入對惰性求值的好處有限,大致和前文所述一致,但至少我們可以定義類型通用的 接口了:

// 一個適用於線性結構的迭代器接口
type Iter[T any] interface{ Next() (T, bool) }

// 用於將任意 slice 包裝成 Iter[T]
type SliceIter[T any] struct {
        i int
        s []T
}

func IterOfSlice[T any]([]"T any") Iter[T] {
        return &SliceIter[T]{s: s}
}

func (i *SliceIter[T]) Next() (v T, ok bool) {
        if ok = i.i < len(i.s); ok {
                v = i.s[i.i]
                i.i++
        }
        return
}

接着實現惰性版本的 filter:

type filterIter[T any] struct {
        f   func(T) bool
        src Iter[T]
}

func (i *filterIter[T]) Next() (v T, ok bool) {
        for {
                v, ok = i.src.Next()
                if !ok || i.f(v) {
                        return
                }
        }
}

func Filter[T any](f func("T any") bool, src Iter[T]) Iter[T] {
        return &filterIter[T]{f: f, src: src}
}

可以看到這個版本的 filter 僅僅返回了一個 Iter[T]*filterIter[T]),實際的運算在 *filterIter[T].Next() 中進行。

我們還需要一個將 Iter[T] 轉回 []T 的函數:

func List[T any](src Iter[T] "T any") (dst []T) {
        for {
                v, ok := src.Next()
                if !ok {
                        return
                }
                dst = append(dst, v)
        }
}

最後實現一個和上面等價的運算,但實際的計算工作是在 List(i) 的調用中發生的:

i := IterOfSlice([]int{-2, -1, -0, 1, 2})
i = Filter(func(v int) bool { return v > -2 }, i)
i = Filter(func(v int) bool { return v < 2 }, i)
i = Filter(func(v int) bool { return v != 0 }, i)
fmt.Println(List(i))

Map 的迭代器

Golang 中的 Hashmap map[K]V 和 Slice []T 一樣是常用的數據結構,如果我們能將 map 轉化爲上述的 Iter[T],那麼 map 就能直接使用已經實現的各種高階函數。

map[K]V 的迭代只能通過 for ... range 進行,我們無法通過常規的手段獲得一個 iterator。反射當然可以做到,但 reflect.MapIter 太重了。modern-go/reflect2[19] 提供了一個 更快的實現 [20] ,但已經超出了本文的討論範圍,此處不展開,有興趣的朋友可以自行研究。

局部應用

局部應用 [21] (Partial Application)是一種固定多參函數的部分參數,並返回一個可以接受剩餘部分參數的函數的操作。

備註

局部應用不同於 📖 柯里化 [22] (Currying) Partial Function Application is not Currying[23],柯里化是一種用多個單參函數來表示多參函數的技術,在 Go 已經支持多參函數的情況下,本文暫時不討論 Currying 的實現。

我們定義一個有返回值的接收單個參數的函數類型:

type FuncWith1Args[A, R any] func(A) R

對一個只接受一個參數的函數進行一次 partial application,其實就相當於求值:

func (f FuncWith1Args[A, R]) Partial(a A) R {
        return f(a)
}

接受兩個參數的函數被 partial application 後,一個參數被固定,自然返回一個上述的 FuncWith1Args:

type FuncWith2Args[A1, A2, R any] func(A1, A2) R

func (f FuncWith2Args[A1, A2, R]) Partial(a1 A1) FuncWith1Args[A2, R] {
        return func(a2 A2) R {
                return f(a1, a2)
        }
}

我們來試用一下,將我們之前實現的 filter 包裝成一個 FuncWith2Args,從左到右固定兩個參數,最後得到結果:

f2 := FuncWith2Args[func(int) bool, Iter[int], Iter[int]](Filter[int] "func(int) bool, Iter[int], Iter[int]")
f1 := f2.Partial(func(v int) bool { return v > -2 })
r := f1.Partial(IterOfSlice([]int{-2, -1, -0, 1, 2}))
fmt.Println(List(r))
// Output:
// [-1 0 1 2]

類型參數推導

我們勉強實現了 partial application,可是把 Filter 轉換爲 FuncWith2Args 的過程太過繁瑣,在上面的例子中,我們把類型參數完整地指定了一遍,是不是重新感受到了 閉包語法 [24] 帶給你的無奈?

這一次我們並非無能爲力,提案中的 #Type inference[25] 一節描述了對類型參數推導的支持情況。上例的轉換毫無歧義,那我們把類型參數去掉:

// INVALID CODE!!!
f2 := FuncWith2Args(Filter[int])

編譯器如是抱怨:

cannot use generic type FuncWith2Args without instantiation

提案裏的類型參數推導僅針對函數調用,FuncWith2Args(XXX) 雖然看起來像是函數調用語法,但其實是一個類型的實例化,針對類型實例化的參數類型推導( #Type inference for composite literals[26] )還是一個待定的 feature。

如果我們寫一個函數來實例化這個對象呢?很遺憾,做不到:我們用什麼表示入參呢?只能寫出這樣「聽君一席話,如聽一席話」的函數:

func Cast[A1, A2, R any](f FuncWith2Args[A1, A2, R] "A1, A2, R any") FuncWith2Args[A1, A2, R] {
        return f
}

但是它能工作!當我們直接傳入 Filter 的時候,編譯器會幫我們隱式地轉換成一個 FuncWith2Args[func(int) bool, Iter[int], Iter[int]]!同時因爲函數類型參數推導的存在,我們不需要指定任何的類型參數了:

f2 := Cast(Filter[int])
f1 := f2.Partial(func(v int) bool { return v > -2 })
r := f1.Partial(IterOfSlice([]int{-2, -1, -0, 1, 2}))
fmt.Println(List(r))
// Output:
// [-1 0 1 2]

可變類型參數

FuncWith1ArgsFuncWith2Args 這些名字讓我們有些恍惚,彷彿回到了代碼生成的時代。爲了處理更多的參數,我們還得寫 FuncWith3ArgsFuncWith4Args… 嗎?

是的, #Omissions[27] 一節提到:Go 的泛型不支持可變數目的類型參數:

No variadic type parameters. There is no support for variadic type parameters, which would permit writing a single generic function that takes different numbers of both type parameters and regular parameters.

對應到函數簽名,我們也沒有語法來聲明擁有不同類型的可變參數。

類型系統

衆多函數式特性的實現依賴於一個強大類型系統,Go 的類型系統顯然不足以勝任,作者不是專業人士,這裏我們不討論其他語言裏讓人羨慕的類型類(Type Class)、代數數據類型(Algebraic Data Type),只討論在 Go 語言中引入泛型之後,我們的類型系統有哪些水土不服的地方。

提示

其實上文的大部分問題都和類型系統息息相關,case by case 的話我們可以列出非常多的問題,因此以下只展示明顯不合理那部分。

編譯期類型判斷

當我們在寫一段泛型代碼裏的時候,有時候會需要根據 T 實際上的類型決定接下來的流程,可 Go 的完全沒有提供在編譯期操作類型的能力。運行期的 workaround 當然有,怎麼做呢:將 T 轉化爲 interface{},然後做一次 type assertion:

func Foo[T any](n T "T any") {
        if _, ok := (interface{})(n).(int); ok {
                // do sth...
        }
}

無法辨認「基礎類型」

我們在 代碼生成之困 [28] 提到過,在類型約束中可以用 ~T 的語法約束所有 基礎類型爲 T 的類型,這是 Go 在語法層面上首次暴露出「基礎類型」的概念,在之前我們只能通過 reflect.(Value).Kind 獲取。而在 type assertion 和 type switch 裏並沒有對應的語法處理「基礎類型」:

type Int interface {
        ~int | ~uint
}

func IsSigned[T Int](n T "T Int") {
        switch (interface{})(n).(type) {
        case int:
                fmt.Println("signed")
        default:
                fmt.Println("unsigned")
        }
}

func main() {
        type MyInt int
        IsSigned(1)
        IsSigned(MyInt(1))
}
// Output:
// signed
// unsigned

乍一看很合理,MyInt 確實不是 int。那我們要如何在函數不瞭解 MyInt 的情況下把它當 int 處理呢?答案是還不能:#Identifying the matched predeclared type[29] 表示這是個未決的問題,需要在後續的版本中討論新語法。總之,在 1.18 中,我們是見不到它了。

類型約束不可用於 type assertion

一個直觀的想法是單獨定義一個 Signed 約束,然後判斷 T 是否滿足 Signed:

type Signed interface {
        ~int
}

func IsSigned[T Int](n T "T Int") {
        if _, ok := (interface{})(n).(Signed); ok {
                fmt.Println("signed")
        } else {
                fmt.Println("unsigned")
        }
}

但很可惜,類型約束不能用於 type assertion/switch,編譯器報錯如下:

interface contains type constraints

儘管讓類型約束用於 type assertion 可能會引入額外的問題,但犧牲這個支持讓 Go 的類型表達能力大大地打了折扣。

總結

函數式編程的特性不止於此,代數數據類型、引用透明(Referential Transparency)等在本文中都未能覆蓋到。總得來說,Go 泛型的引入:

  1. 使的部分 函數式特性能以更通用的方式被實現

  2. 靈活度比代碼生成更高 ,用法更自然,但細節上的小問題很多

  3. 1.18 的泛型在引入 type paramters 語法之外並沒有其他大刀闊斧的改變,導致泛型和這個語言的其他部分顯得有些格格不入,也使得泛型的能力受限。至少在 1.18 裏,我們要忍受泛型中存在的種種不一致

  4. 受制於 Go 類型系統的表達能力,我們無法表示複雜的類型約束,自然也 無法實現完備的函數式特性

參考資料

[1]

Golang 函數式編程簡述: https://hedzr.com/golang/fp/golang-functional-programming-in-brief/

[2]

GopherCon 2020: Dylan Meeus - Functional Programming with Go: https://www.youtube.com/watch?v=wqs8n5Uk5OM

[3]

spec: add generic programming using type parameters #43651: https://github.com/golang/go/issues/43651

[4]

Type Parameters Proposal: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md

[5]

從源碼編譯: https://golang.org/doc/install/source#install

[6]

The go2go Playground: https://go2goplay.golang.org/

[7]

#Very high level overview: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#very-high-level-overview

[8]

📖 高階函數: https://zh.wikipedia.org/wiki / 高階函數

[9]

代碼生成的例子: https://github.com/golang/go/search?q=filename%3Agen.go

[10]

hasgo: https://pkg.go.dev/github.com/DylanMeeus/hasgo/types?utm_source=godoc#Ints.Map

[11]

functional-go: https://pkg.go.dev/github.com/logic-building/functional-go/fp

[12]

fpGo: https://pkg.go.dev/github.com/TeaEntityLab/fpGo#Map

[13]

Golang 函數式編程簡述: https://hedzr.com/golang/fp/golang-functional-programming-in-brief/

[14]

proposal: Go 2: Lightweight anonymous function syntax #21498: https://github.com/golang/go/issues/21498

[15]

鏈式調用: https://wikipedia.org/wiki/Method_chaining

[16]

#No parameterized methods: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#No-parameterized-methods

[17]

1: https://silverrainz.me/blog/funtional-programming-in-go-generics.html#id39

[18]

📖 惰性求值: https://zh.wikipedia.org/wiki / 惰性求值

[19]

K]V的迭代只能通過for ... range進行,我們無法通過常規的手段獲得一個 iterator。反射當然可以做到,但reflect.MapIter` 太重了。[modern-go/reflect2: https://github.com/modern-go/reflect2

[20]

更快的實現: https://pkg.go.dev/github.com/modern-go/reflect2#UnsafeMapIterator

[21]

局部應用: https://wikipedia.org/wiki/Partial_application

[22]

📖 柯里化: https://zh.wikipedia.org/wiki / 柯里化

[23]

Partial Function Application is not Currying: https://www.uncarved.com/articles/not-currying/

[24]

閉包語法: https://silverrainz.me/blog/funtional-programming-in-go-generics.html#id18

[25]

#Type inference: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#type-inference

[26]

#Type inference for composite literals: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#type-inference-for-composite-literals

[27]

#Omissions: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#omissions

[28]

代碼生成之困: https://silverrainz.me/blog/funtional-programming-in-go-generics.html#id12

[29]

#Identifying the matched predeclared type: https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#identifying-the-matched-predeclared-type

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/wPLH4agJr-LozUsOqwN08g