Golang函數(shù)式編程簡述

看起來很美好，但為什么不用 map 操作舉例呢？我們很容易寫出這樣的方法簽名:

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

很遺憾這樣的代碼是沒法通過編譯的，我們會獲得以下錯(cuò)誤：

invalid AST: method must have no type parameter

提案的 #No parameterized methods^[16] 一節(jié)明確表示了方法（method，也就是有 recevier 的函數(shù)）不支持單獨(dú)指定類型參數(shù)：

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]

這個(gè)決定實(shí)際上是個(gè)不得已的妥協(xié)。假設(shè)我們實(shí)現(xiàn)了上述的方法，就意味對于一個(gè)已經(jīng)實(shí)例化了的 List[T] 對象（比如說 List[int]），它的 Map 方法可能有多個(gè)版本：Map(func (int) int) List[int] 或者 Map(func (int) string) List[string]，當(dāng)用戶的代碼調(diào)用它們時(shí)，它們的代碼必然在之前的某個(gè)時(shí)刻生成了，那么應(yīng)該在什么時(shí)候呢？

1. 在編譯期，更準(zhǔn)確地說，在編譯的 link 階段，這需要 linker 去遍歷整個(gè) call graph，確定程序中到底使用了幾個(gè)版本的 Map。問題在于反射（reflection）的存在：用戶可以用 reflect.MethodByName 動(dòng)態(tài)地調(diào)用對象的方法，所以即使遍歷了整個(gè) call graph，我們也無法確保用戶的代碼到底調(diào)用了幾個(gè)版本的 Map
2. 在運(yùn)行期，在第一次調(diào)用方法時(shí) yield 到 runtime 中，生成對應(yīng)版本的函數(shù)后 resume 回去，這要求 runtime 支持 JIT（Just-in-time compilation），而目前 Go 并不支持，即使未來 JIT 的支持提上日程，這也不是一蹴而就的事情

綜上，Go 團(tuán)隊(duì)選擇了不支持給 method 指定類型參數(shù)，完美了解決這個(gè)問題 。

惰性求值

惰性求值^[18] （Lazy Evaluation）是另一個(gè)重要的函數(shù)式特性，一個(gè)不嚴(yán)謹(jǐn)?shù)拿枋鍪牵涸诙x運(yùn)算時(shí)候，計(jì)算不會發(fā)生，直到我們需要這個(gè)值的時(shí)候才進(jìn)行。其優(yōu)點(diǎn)在于能使計(jì)算在空間復(fù)雜度上得到極大的優(yōu)化。

下面的代碼展示了一個(gè)平平無奇的 Add 函數(shù)和它的 Lazy 版本，后者在給出加數(shù)的時(shí)候不會立刻計(jì)算，而是返回一個(gè)閉包:

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

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

上面這個(gè)例子沒有體現(xiàn)出惰性求值節(jié)省空間的優(yōu)點(diǎn)?；谖覀冎皩?shí)現(xiàn)的高階函數(shù)，做以下的運(yùn)算:

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?return?v?!=?0?},?l)
fmt.Println(l)

計(jì)算過程中會產(chǎn)生 3 個(gè)新的長度為 5 的 []int，空間復(fù)雜度為 O(3?N)，盡管常數(shù)在復(fù)雜度分析時(shí)經(jīng)常被省略，但在程序?qū)嶋H運(yùn)行的時(shí)候，這里的 3 就意味著 3 倍的內(nèi)存占用。

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

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

//?一個(gè)適用于線性結(jié)構(gòu)的迭代器接口
type?Iter[T?any]?interface{?Next()?(T,?bool)?}

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

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

func?(i?*SliceIter[T])?Next()?(v?T,?ok?bool)?{
????????if?ok?=?i.i?return
}

接著實(shí)現(xiàn)惰性版本的 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?"T?any")?bool,?src?Iter[T])?Iter[T]?{
????????return?&filterIter[T]{f:?f,?src:?src}
}

可以看到這個(gè)版本的 filter 僅僅返回了一個(gè) Iter[T]（*filterIter[T]），實(shí)際的運(yùn)算在 *filterIter[T].Next() 中進(jìn)行。

我們還需要一個(gè)將 Iter[T] 轉(zhuǎn)回 []T 的函數(shù):

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

最后實(shí)現(xiàn)一個(gè)和上面等價(jià)的運(yùn)算，但實(shí)際的計(jì)算工作是在 List(i) 的調(diào)用中發(fā)生的:

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?return?v?!=?0?},?i)
fmt.Println(List(i))

Map 的迭代器

Golang 中的 Hashmap map[K]V 和 Slice []T 一樣是常用的數(shù)據(jù)結(jié)構(gòu)，如果我們能將 map 轉(zhuǎn)化為上述的 Iter[T]，那么 map 就能直接使用已經(jīng)實(shí)現(xiàn)的各種高階函數(shù)。

map[K]V 的迭代只能通過 for ... range 進(jìn)行，我們無法通過常規(guī)的手段獲得一個(gè) iterator。反射當(dāng)然可以做到，但 reflect.MapIter 太重了。modern-go/reflect2^[19] 提供了一個(gè) 更快的實(shí)現(xiàn)^[20] ，但已經(jīng)超出了本文的討論范圍，此處不展開，有興趣的朋友可以自行研究。

局部應(yīng)用

局部應(yīng)用^[21] （Partial Application）是一種固定多參函數(shù)的部分參數(shù)，并返回一個(gè)可以接受剩余部分參數(shù)的函數(shù)的操作。

備注

局部應(yīng)用不同于 柯里化^[22] （Currying） Partial Function Application is not Currying^[23]，柯里化是一種用多個(gè)單參函數(shù)來表示多參函數(shù)的技術(shù)，在 Go 已經(jīng)支持多參函數(shù)的情況下，本文暫時(shí)不討論 Currying 的實(shí)現(xiàn)。

我們定義一個(gè)有返回值的接收單個(gè)參數(shù)的函數(shù)類型:

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

對一個(gè)只接受一個(gè)參數(shù)的函數(shù)進(jìn)行一次 partial application，其實(shí)就相當(dāng)于求值:

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

接受兩個(gè)參數(shù)的函數(shù)被 partial application 后，一個(gè)參數(shù)被固定，自然返回一個(gè)上述的 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)
????????}
}

我們來試用一下，將我們之前實(shí)現(xiàn)的 filter 包裝成一個(gè) FuncWith2Args，從左到右固定兩個(gè)參數(shù)，最后得到結(jié)果:

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]

類型參數(shù)推導(dǎo)

我們勉強(qiáng)實(shí)現(xiàn)了 partial application，可是把 Filter 轉(zhuǎn)換為 FuncWith2Args 的過程太過繁瑣，在上面的例子中，我們把類型參數(shù)完整地指定了一遍，是不是重新感受到了 閉包語法^[24] 帶給你的無奈？

這一次我們并非無能為力，提案中的 #Type inference^[25] 一節(jié)描述了對類型參數(shù)推導(dǎo)的支持情況。上例的轉(zhuǎn)換毫無歧義，那我們把類型參數(shù)去掉:

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

編譯器如是抱怨：

cannot use generic type FuncWith2Args without instantiation

提案里的類型參數(shù)推導(dǎo)僅針對函數(shù)調(diào)用，FuncWith2Args(XXX) 雖然看起來像是函數(shù)調(diào)用語法，但其實(shí)是一個(gè)類型的實(shí)例化，針對類型實(shí)例化的參數(shù)類型推導(dǎo)（ #Type inference for composite literals^[26] ）還是一個(gè)待定的 feature。

如果我們寫一個(gè)函數(shù)來實(shí)例化這個(gè)對象呢？很遺憾，做不到：我們用什么表示入?yún)⒛?？只能寫出這樣「聽君一席話，如聽一席話」的函數(shù):

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

但是它能工作！當(dāng)我們直接傳入 Filter 的時(shí)候，編譯器會幫我們隱式地轉(zhuǎn)換成一個(gè) FuncWith2Args[func(int) bool, Iter[int], Iter[int]]！同時(shí)因?yàn)楹瘮?shù)類型參數(shù)推導(dǎo)的存在，我們不需要指定任何的類型參數(shù)了:

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]

可變類型參數(shù)

FuncWith1Args 、FuncWith2Args 這些名字讓我們有些恍惚，仿佛回到了代碼生成的時(shí)代。為了處理更多的參數(shù)，我們還得寫 FuncWith3Args、FuncWith4Args… 嗎？

是的， #Omissions^[27] 一節(jié)提到：Go 的泛型不支持可變數(shù)目的類型參數(shù)：

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.

對應(yīng)到函數(shù)簽名，我們也沒有語法來聲明擁有不同類型的可變參數(shù)。

類型系統(tǒng)

眾多函數(shù)式特性的實(shí)現(xiàn)依賴于一個(gè)強(qiáng)大類型系統(tǒng)，Go 的類型系統(tǒng)顯然不足以勝任，作者不是專業(yè)人士，這里我們不討論其他語言里讓人羨慕的類型類（Type Class）、代數(shù)數(shù)據(jù)類型（Algebraic Data Type），只討論在 Go 語言中引入泛型之后，我們的類型系統(tǒng)有哪些水土不服的地方。

提示

其實(shí)上文的大部分問題都和類型系統(tǒng)息息相關(guān)，case by case 的話我們可以列出非常多的問題，因此以下只展示明顯不合理那部分。

編譯期類型判斷

當(dāng)我們在寫一段泛型代碼里的時(shí)候，有時(shí)候會需要根據(jù) T 實(shí)際上的類型決定接下來的流程，可 Go 的完全沒有提供在編譯期操作類型的能力。運(yùn)行期的 workaround 當(dāng)然有，怎么做呢：將 T 轉(zhuǎn)化為 interface{}，然后做一次 type assertion:

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

無法辨認(rèn)「基礎(chǔ)類型」

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

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 確實(shí)不是 int。那我們要如何在函數(shù)不了解 MyInt 的情況下把它當(dāng) int 處理呢？答案是還不能：#Identifying the matched predeclared type^[29] 表示這是個(gè)未決的問題，需要在后續(xù)的版本中討論新語法?？傊?1.18 中，我們是見不到它了。

類型約束不可用于 type assertion

一個(gè)直觀的想法是單獨(dú)定義一個(gè) 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，編譯器報(bào)錯(cuò)如下：

interface contains type constraints

盡管讓類型約束用于 type assertion 可能會引入額外的問題，但犧牲這個(gè)支持讓 Go 的類型表達(dá)能力大大地打了折扣。

總結(jié)

函數(shù)式編程的特性不止于此，代數(shù)數(shù)據(jù)類型、引用透明（Referential Transparency）等在本文中都未能覆蓋到?？偟脕碚f，Go 泛型的引入：

1. 使的部分 函數(shù)式特性能以更通用的方式被實(shí)現(xiàn)
2. 靈活度比代碼生成更高 ，用法更自然，但細(xì)節(jié)上的小問題很多
3. 1.18 的泛型在引入 type paramters 語法之外并沒有其他大刀闊斧的改變，導(dǎo)致泛型和這個(gè)語言的其他部分顯得有些格格不入，也使得泛型的能力受限。至少在 1.18 里，我們要忍受泛型中存在的種種不一致
4. 受制于 Go 類型系統(tǒng)的表達(dá)能力，我們無法表示復(fù)雜的類型約束，自然也 無法實(shí)現(xiàn)完備的函數(shù)式特性

　　審核編輯：湯梓紅