函数式编程在 Go 泛型下的实用性探索

背景

函数式编程（Functional Programming / FP）作为一种编程范式，具有无状态、无副作用、并发友好、抽象程度高等优点。目前流行的编程语言（C++、Python、Rust）都或多或少地引入了函数式特性，但在同作为流行语言的 Golang 中却少有讨论。

究其原因，大部分的抱怨Golang 函数式编程简述 、GopherCon 2020: Dylan Meeus - Functional Programming with Go集中于 Go 缺乏对泛型的支持，难以写出类型间通用的函数。代码生成只能解决一部分已知类型的处理，且无法应对类型组合导致复杂度（比如实现一个通用的 TypeA → TypeB 的 map 函数）。

有关泛型的提案 spec: add generic programming using type parameters #43651已经被 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

基于这个重大特性，我们有理由重新看看，函数式特性在 Go 泛型的加持下，能否变得比以往更加实用。

概述

这篇文章里，我们会尝试用 Go 的泛型循序渐进地实现一些常见的函数式特性，从而探索 Go 泛型的优势和不足。

// INVALID CODE!!!package mainmain

泛型语法

提案的 #Very high level overview一节中描述了为泛型而添加的新语法，这里简单描述一下阅读本文所需要的语法：

func F[T any](p T "T any") { ... }type M[T any] []TanyinterfaceinterfaceTT|~TTtype MyInt intInteger1

提示
「基础类型」在提案中为 “underlying type”，目前尚无权威翻译，在本文中使用仅为方便描述。

高阶函数

在函数式编程语言中，高阶函数（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

func (T) bool[] Ttrue

根据上面的泛型语法，我们可以很容易地写出一个简单的 filter 函数:

func Filter[T any](f func(T "T any") bool, src []T) []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 函数有两种方式：

interface{}FilterIntFilterString

方式 2 的缺点可以通过代码生成规避，具体来说就使用相同的一份模版，以数据类型为变量生成不同的实现。我们在 Golang 内部可以看到不少 代码生成的例子 。

那么，有了代码生成，我们是不是就不需要泛型了呢？

答案是否定的：

float64intinterface{}func (T1) T2[]T1[]T2MapIntIntMapIntUintMapIntString

[]T → []T

无糖的泛型

<-

闭包语法

在 Haskell 中的匿名函数形式非常简洁：

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

而在 Golang 里，函数的类型签名不可省略，无论高阶函数要求何种签名，调用者在构造闭包的时候总是要完完整整地将其照抄一遍Golang 函数式编程简述

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提出了一个简化闭包调用语法的提案，但即使该提案被 accept，我们最快也只能在 Go 2 里见到它了。

方法类型参数

链式调用（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一节明确表示了方法（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

List[T]List[int]MapMap(func (int) int) List[int]Map(func (int) string) List[string]

Mapreflect.MethodByNameMap

综上，Go 团队选择了不支持给 method 指定类型参数，完美了解决这个问题 。

惰性求值

惰性求值（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)

[]int

fmt.Printlnlif v > -2if v < 2v + 1[]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](s []T "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 "T any") bool, src Iter[T]) Iter[T] {
        return &filterIter[T]{f: f, src: src}
}

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 的迭代器

map[K]V[]TIter[T]

map[K]Vfor ... rangereflect.MapIter

局部应用

局部应用[21] （Partial Application）是一种固定多参函数的部分参数，并返回一个可以接受剩余部分参数的函数的操作。

备注

局部应用不同于 柯里化（Currying） Partial Function Application is not Currying，柯里化是一种用多个单参函数来表示多参函数的技术，在 Go 已经支持多参函数的情况下，本文暂时不讨论 Currying 的实现。

我们定义一个有返回值的接收单个参数的函数类型:

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

对一个只接受一个参数的函数进行一次 partial application，其实就相当于求值:

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

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

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]

类型参数推导

FilterFuncWith2Args

这一次我们并非无能为力，提案中的 #Type inference一节描述了对类型参数推导的支持情况。上例的转换毫无歧义，那我们把类型参数去掉:

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

编译器如是抱怨：

cannot use generic type FuncWith2Args without instantiation

FuncWith2Args(XXX)

如果我们写一个函数来实例化这个对象呢？很遗憾，做不到：我们用什么表示入参呢？只能写出这样「听君一席话，如听一席话」的函数:

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

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]

可变类型参数

FuncWith1ArgsFuncWith2ArgsFuncWith3ArgsFuncWith4Args

是的， #Omissions一节提到：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 的话我们可以列出非常多的问题，因此以下只展示明显不合理那部分。

编译期类型判断

TTinterface{}

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

无法辨认「基础类型」

~TTreflect.(Value).Kind

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

MyIntintMyIntint

类型约束不可用于 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 类型系统的表达能力，我们无法表示复杂的类型约束，自然也 无法实现完备的函数式特性