Go语言参数多态初探：设计通用双向映射

本文深入探讨Go语言中参数多态（泛型）的应用，通过设计一个通用的双向映射数据结构，展示泛型如何提升代码灵活性和类型安全性，同时保持API的简洁和易用性。

Go语言参数多态初探：设计通用双向映射

TL;DR ¶ 为了熟悉Go语言类型参数的最新设计草案，我编写了一个双向映射的泛型实现。你可以在这个playground中尝试它。

编辑（2022-04-03）：现在Go 1.18已经发布，我对这篇文章进行了一些更新。

泛型即将来到Go ¶

Go语言对参数多态（俗称“泛型”）的支持正在积极开发中。上个月，Go团队发布了一篇博客文章，详细介绍了他们在这方面的进展。Johnny Boursiquot和Jaana B. Dogan对这一宣布反应热烈，这促使我阅读了更新的设计草案，并亲自尝试了Go泛型！

为什么泛型重要 ¶

在继续阅读本文之前，如果你不知道泛型是什么，或者怀疑它们是否适合Go，我建议你阅读Ian Lance Taylor 2019年关于这个话题的文章。

撰写本文时，Go的最新版本（v1.14）不支持泛型。因此，追求最大灵活性的库作者通常别无选择，只能到处使用空接口（interface{}）（例如，参见sync.Map）。不幸的是，这种设计选择的后果在客户端代码中会强烈感受到。空接口是一种如此不加区分的抽象类型，它不提供关于底层具体类型可能表现出的行为的编译时保证。库的用户被迫在代码中大量使用类型断言，以操作隐藏在interface{}下的具体类型。

泛型声称要解决这个问题：它们承诺在不牺牲可用性或类型安全性的情况下，提供更灵活的代码。然而，关于向Go添加泛型的一些合理问题仍然存在。它是否会不利地影响编译速度？更重要的是，它是否会显著损害Go的简洁性议程？它是否会极大地复杂化编写、阅读和使用Go代码？找到其中一些问题的答案是我撰写本文的主要动机。

泛型设计草案的重要变化 ¶

我不会在这里深入细节；你可以阅读更新的设计草案以获取完整信息。以下是我从中得到的主要要点。

合约已消失 ¶

最重要的是，合约已从设计草案中删除。得益于参数多态专家（和λ演算超级英雄）Phil Wadler及其合作者的见解，Go团队能够将合约统一到现有的接口概念下。我认为这是朝着正确方向迈出的重要一步，主要有两个原因：

  • 合约的概念总是与接口的概念混淆不清，但又有所不同。我记得这条模糊的界线给我造成了心理障碍：这可能解释了为什么我在最近更新之前没有深入研究泛型设计草案。
  • 不再需要添加合约关键字，这原本需要在源代码级别与Go 1.0不兼容。

当前的草案提案仍然需要对语言进行更改，但这些更改预计对大多数程序 largely inconsequential。

新的可比较接口 ¶

另一个显著的变化是添加了一个名为comparable的接口类型，作为语言中的预声明名称。你猜对了：comparable表示可以使用==和!=运算符进行比较的类型。

泛型的一个用例：双向映射 ¶

在阅读了更新的设计草案后，我翻阅了个人笔记，寻找Go库和程序中泛型的有趣用例，于是泛型双向映射的想法出现了。

根据维基百科，双向映射是

一种关联数据结构，其中键值对形成一一对应关系。因此，二元关系在每个方向上都是函数性的：每个值也可以映射到唯一的键。

换句话说，双向映射是一种类似于常规映射的抽象，但强制执行以下不变量：每个值都与且仅与一个键关联。

在我的一个副项目中，我最近遇到了一个双向映射的用例（如果你必须知道，是一个标签系统）。一个非泛型实现（字符串到字符串）解决了问题，但它让我想知道：

  • 泛型实现会是什么样子？
  • 向语言添加泛型如何改变Go包的API设计？
  • 使用这样的包会感觉多么自然？

好奇心太强，我无法抗拒，于是开始设计一个Go API用于泛型双向映射。

泛型双向映射的API设计 ¶

首先，在深入可能的实现之前，让我概述一下我想要实现的目标。

bimap包及其导出的Bimap类型 ¶

目标是编写一个名为bimap的包，它导出一个（具体）泛型双向映射类型，名为Bimap。这种类型应该接受两个可比较的类型参数，一个用于键，一个用于值。

零值应该立即可用 ¶

Josh Bloch在API设计中的一个重要教训，它标志了我的Java时代，并一直伴随着我，那就是

[…] 不仅应该容易使用一个好的API，而且应该难以误用一个好的API。

设计一个类型，使其零值对应于有效状态，是Go中的一个重要原则，因为它有助于使类型的API难以误用。

工厂函数和方法 ¶

bimap应该为Bimap提供一个工厂函数；按照惯例，这样的函数名为New。以下是Bimap的方法列表：

1
2
3
4
5
6
7

func (bi *Bimap[K, V]) Store(key K, value V)
func (bi *Bimap[K, V]) LoadValue(k K) (V, bool)
func (bi *Bimap[K, V]) LoadKey(v V) (K, bool)
func (bi *Bimap[K, V]) DeleteByKey(k K)
func (bi *Bimap[K, V]) DeleteByValue(v V)
func (bi *Bimap[K, V]) Size() int
func (bi *Bimap[K, V]) String() string

我为其中一些方法名称的冗长道歉，但我希望它们反映数据结构的对称性：键和值的角色确实可以互换而没有后果。注意，所有这些方法都使用指针接收器：它们中的大多数需要改变Bimap的内部状态，并且不鼓励在单个类型中混合指针和值接收器。

Store在双向映射中存储一个键值对。可能有几种语义，但一个自然的设计选择是静默删除涉及提供的键或提供的值的预先存在的对。

LoadValue返回存储在双向映射中的键的值和一个布尔值，该布尔值指示是否找到了相关的键；LoadKey是LoadValue的对称操作。

DeleteByKey和DeleteByValue分别删除与给定键或值关联的键值对。

Size返回双向映射中键值对的数量。

最后，Keys返回键的切片，Values返回值的切片，顺序不确定。

我的bimap包的API故意最小化。特别是，Bimap缺少一个Range方法；我留给你作为练习。然而，为了可视化目的，我将使Bimap成为一个Stringer，带有一个简单的String实现。

一个可能的实现 ¶

双向映射的一个非常常见的实现涉及维护两个映射，一个从键到值，另一个从值到键；至少对于这种数据结构的参考实现来说，这是一个不错的起点。

因为Bimap将持有至少两个映射，所以其底层类型最自然的选择是结构体。所有这些设计决策导致我们为Bimap声明以下类型：

1
2
3
4

type Bimap[K, V comparable] struct {
	forward map[K]V
	inverse map[V]K
}

类型参数K和V，被约束为可比较，在类型名称后的方括号中引入。为了封装目的，结构体完全不透明，即，没有字段被导出：否则，bimap包的用户将能够直接弄乱Bimap的内部并破坏其不变量。

编写bimap包的其余部分相对简单：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

func (bi *Bimap[K, V]) Store(key K, value V) {
	k, exists := bi.inverse[value]
	if exists { // value is already associated with k
		delete(bi.forward, k)
	}
	v, exists := bi.forward[key]
	if exists { // key is already associated with v
		delete(bi.inverse, v)
	}
	if bi.forward == nil { // bi hasn't been initialised yet
		bi.forward = make(map[K]V)
		bi.inverse = make(map[V]K)
	}
	bi.forward[key] = value
	bi.inverse[value] = key
}

func (bi *Bimap[K, V]) LoadValue(k K) (V, bool) {
	v, ok := bi.forward[k]
	return v, ok
}

func (bi *Bimap[K, V]) LoadKey(v V) (K, bool) {
	k, ok := bi.inverse[v]
	return k, ok
}

func (bi *Bimap[K, V]) DeleteByKey(k K) {
	v := bi.forward[k]
	delete(bi.forward, k)
	delete(bi.inverse, v)
}

func (bi *Bimap[K, V]) DeleteByValue(v V) {
	k := bi.inverse[v]
	delete(bi.inverse, v)
	delete(bi.forward, k)
}

func (bi *Bimap[K, V]) Size() int {
	return len(bi.forward)
}

func (bi *Bimap[K, V]) Keys() []K {
	var keys []K
	for k := range bi.forward {
		keys = append(keys, k)
	}
	return keys
}

func (bi *Bimap[K, V]) Values() []V {
	var values []V
	for v := range bi.inverse {
		values = append(values, v)
	}
	return values
}

func (bi *Bimap[K, V]) String() string {
	return fmt.Sprintf("Bi%v", bi.forward)
}

编辑（2020-07-23）：Store包含一个错误；参见附录。

注意，根据当前的设计草案，泛型接收器必须指定类型所需的所有类型参数，即使其中一些类型参数未在方法体中使用。例如，将Size声明如下

1

func (bi *Bimap[_, _]) Size() int

是非法的。能够在这种地方使用空白标识符当然会很好，但我不知道这是否在计划中。我只是在这里推测，但也许在编译器中实现这个功能会使单态化复杂化…

我的bimap包的完整源代码，以及测试套件，可在我的jub0bs/bimap GitHub仓库中找到。

使用bimap包 ¶

一旦为Bimap指定了具体类型（在设计草案中称为实例化的过程），客户端代码的其余部分对我来说感觉就像泛型之前的Go代码一样自然：

1
2
3
4
5

bi := bimap.New[int, string]()
bi.Store(0, "Planets&Stars")
bi.Store(1, "Chemistry")
bi.Store(0, "Astronomy")
bi.DeleteByValue("Chemistry")

你觉得怎么样？

结论 ¶

双向映射可以说是Go中泛型的一个非常简单的用例，但它让你对泛型代码的样子有了一些了解，如果设计草案被接受且几乎没有修改的话。

泛型的伟大之处在于，这个bimap包只需要编写一次，并且可以用于键和值的任何（可比较）具体类型的组合。作为库作者，我觉得这很解放。

此外，我怀疑泛型代码用户所需的额外认知负荷是否会证明是禁止的。泛型在其他语言中可能被合理恐惧，但缺乏继承使得Go泛型相对更容易理解。就我而言：Go泛型获胜！

附录（2020/07/23） ¶

不幸的是，正如Martin Möhrmann在Gophers Slack工作区向我指出的那样，NaN（非数字）抛出了一个扳手，并揭示了我原始Bimap实现中的一个微妙错误。

Bimap类型使用两个后备映射，而映射对于等式不是自反的键（即，k使得k == k评估为false）表现出相当奇怪的行为。等式对于NaN和任何包含NaN的复合类型或定义类型的值不是自反的。因为它们的类型是可比较的，所以这样的值可以合法地作为键添加到映射中，但它们不能被加载或删除；在这个playground中自己检查一下。

因此，在存储这样的值之后，我原始Bimap实现的不变量可能会被破坏；在这个playground中查看一个例子。

乍一看，这个未预见到的困难似乎无法逃避…然而，一个简单的出路，除了改变Bimap的内部表示之外，是禁止存储等式不是自反的键和值。

我可以定义一个泛型谓词来检查等式是否对其参数自反，

1
2
3

func isEqualityReflexive[T comparable](t T) bool {
	return t == t
}

并在将键值对添加到Bimap之前，检查传递给Store方法的键和值都满足这个谓词。

而不是静默拒绝不允许的值，可以修改Store以返回操作是否成功：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Store creates a key-value pair and returns whether or not the
// operation was successful. Pre-existing key-value pairs (if any)
// that involve the given key and/or the given value are silently
// removed from the Bimap. Keys and values for which equality is
// not reflexive are disallowed.
func (bi *Bimap[K, V]) Store(key K, value V) bool {
	if !isEqualityReflexive(key) || !isEqualityReflexive(value) {
		return false
	}
	k, exists := bi.inverse[value]
	if exists { // value is already associated with k
		delete(bi.forward, k)
	}
	v, exists := bi.forward[key]
	if exists { // key is already associated with v
		delete(bi.inverse, v)
	}
	if bi.forward == nil { // bi hasn't been initialised yet
		bi.forward = make(map[K]V)
		bi.inverse = make(map[V]K)
	}
	bi.forward[key] = value
	bi.inverse[value] = key
	return true
}

注意，这个布尔结果仅在键类型或值类型或两者都包含此类不允许的值时有用；对于所有其他类型，你可以安全地忽略该结果。

comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次