Go 2のGenericsを使ってリストとHListを作る

はじめに

Go 2とは現在のGo言語の時期バージョンであり現在も開発が進んでいる。まだリリース日などは決まっていないと思われるが、The go2go Playgroundなどで既に試すことができる。現在のGo 1系に比べて色々な機能追加があるが、多くの人が知っている有名な部分として Generics（パラメーター多相）の追加がある。
この記事ではThe go2go Playgroundを利用して、Genericsの入ったGo 2で将来どのようなことができそうなのか？ということをリスト（List）とHListというデータ構造などを例に出しつつ解説する。

Genericsの基本

まずは色々なプログラム言語に存在しているリストの解説を行なっておく。従来のGo 1では構造体などで型パラメーターを取ることができなかったため、リスト構造のためにはキャストや型switchに頼らざるを得ないところがあった。ここではキャストや型switchを使わずにGenericsを利用してリストを作っていく。
なお、利用したコードの全体は下記のURLから入手できる。

• https://go2goplay.golang.org/p/Zv6XdxoXErY

Go 2でのList定義

Go 2では次のように型switchなどを利用しないリスト構造が次のように作成できる。

list.go2

type List[A any] interface { }

type Nil[A any] struct { }

type Cons[A any] struct {
	Head A
	Tail List[A]
}

このようにGo 2では型パラメーターとそれが満すべき制約（type parameter constraint）^[1]をそれぞれ[A any]のように[型パラメーター 制約]という順番で記述する。たとえばintがはいったリストは次のように書ける^[2]。

func main() {
	intList := Cons[int]{1, Cons[int]{2, Cons[int]{3, Nil[int]{}}}}
	
	fmt.Printf("%v", intList)
}

{1 {2 {3 {}}}}

今、インターフェースListにはメソッドが定義されておらず空っぽとなっている。ここにリストの長さを取得するメソッドを次のように追加してみる。

type List[A any] interface {
	Length() int
}

そして次のようにNilとConsにそれぞれLengthメソッドを実装すればOKである。

func (this Nil[A]) Length() int {
	return 0
}

func (this Cons[A]) Length() int {
	return 1 + this.Tail.Length()
}

こうすれば次のようにLengthを使うことができる。

func main() {
	intList := Cons[int]{1, Cons[int]{2, Cons[int]{3, Nil[int]{}}}}
	
	fmt.Printf("%v", intList.Length())
}

危険なリスト定義とその回避

実はこのままだと次のようなListも型が通ってしまう。

func main() {
	illegalList := Cons[int]{1, Cons[int]{2, Cons[bool]{true, Nil[string]{}}}}
	
	fmt.Printf("%v", illegalList.Length())
}

このように3つ目の要素をbool型のtrueにしてみたうえに、最後のNilも型がstringとなるなど、全体的に謎となっている。Consの定義ではTailの型としてHeadの型であるAを利用したList[A]を要請しているので、てっきりこのようなillegalListはコンパイルエラーとなると思っていたが、恐らくGo 2としてはこの時点ではインターフェースList[A any]には型Aな値を直接取り出すようなメソッドが存在しないため、このようなリストが定義できてしまったとしてもキャストなどがない限りは安全であるという立場であると思われる。
したがってインターフェースList[A any]には型パラメーターAに基づく値を返すようなメソッドを追加すればこのようなillegalListはコンパイルエラーになるのではないかということで、次のようなメソッドGetを作成する。

• もしNilであったらGetは値を返さない
• もしConsであったらHeadとTailのペアを返す

Option[A any]とTuple2[A any, B any]

この2つを達成するために、さらにGenericsを使って新たなデータ構造OptionとTuple2を次のように定義する。

type Option[A any] interface { }

type None[A any] struct { }
type Some[A any] struct {
	Value A
}

type Tuple2[A any, B any] struct {
	_1 A
	_2 B
}

前述のとおり、これから作りたいGetメソッドは値を返すまたは返さない、かつ返す場合には2つの値を返す必要がある。このような状況に対応するために、まずはKotlinやSwiftなどでおなじみのOptionを導入する。そして、HeadとTailの2つのまとめて返したいので、それを表現するTuple2も作成しておく。

List.Get()メソッド

これで準備が整ったのでまずはインターフェースList[A any]に次のようなGetメソッドの定義を追加する。

type List[A any] interface {
	Length() int
	Get() Option[Tuple2[A, List[A]]]
}

このように返り値として型パラメーターAを含むようなメソッドが追加された。あとはNilとConsにこのメソッドを実装すればよい。

func (this Nil[A]) Get() Option[Tuple2[A, List[A]]] {
	return None[Tuple2[A, List[A]]]{}
}

func (this Cons[A]) Get() Option[Tuple2[A, List[A]]] {
	return Some[Tuple2[A, List[A]]] {
		Tuple2[A, List[A]] {
			_1: this.Head,
			_2: this.Tail,
		},
	}
}

ここまでやると、さきほどのillegalListは次のようなコンパイルエラーとなる。

type checking failed for main
prog.go2:53:60: cannot use (Nil[string] literal) (value of type Nil[string]) as List[bool] value in struct literal: wrong type for method Get (have func() main.Option[main.Tuple2[A, main.List[A]]], want func() main.Option[main.Tuple2[bool, main.List[bool]]])
prog.go2:53:43: cannot use (Cons[bool] literal) (value of type Cons[bool]) as List[int] value in struct literal: wrong type for method Get (have func() main.Option[main.Tuple2[A, main.List[A]]], want func() main.Option[main.Tuple2[int, main.List[int]]])

このように狙ったとおりのエラーを得ることができた。もちろん全ての要素をintにすればコンパイルに成功する。

Genericsの応用

さて、ここまででも十分に色々なことができることが伝わったかもしれないが、さらに型レベルで複雑なことに挑戦していく。なお完全なコードは下記のURLから手にいれることができる。

• https://go2goplay.golang.org/p/9ESmHxGjHeg

HListの定義

hlist.go2

type HList interface {
    Concat(b HList) HList
}

type HNil[A any] struct { }

type HCons[H any, T HList] struct {
    Head H
    Tail T
}

先ほどのListとは違い、こちらはHCons（ListのConsに相当）の型パラメーターが増えており、かつ制約がanyではなくHListとなっている。このHListがどのようなものなのか？実際に使ってみるのが早いので、次のコードを見てほしい。

func main() {
	hlist := HCons[int, HCons[bool, HCons[string, HNil[interface {}]]]]{
		1, 
		HCons[bool, HCons[string, HNil[interface {}]]]{
			true, 
			HCons[string, HNil[interface {}]]{
				"Hello",
				HNil[interface {}]{},
			},
		},
	}
	fmt.Printf("%v", hlist)
}

{1 {true {Hello {}}}}

型推論が全手動なので量が多いが、HListは色々な型の値を安全に詰めこむことができるリストとなっている^[3]。

HList.Concatの実装

さて、ここからConcat(b HList) HListを作っていくことにする。これは名前のとおりHListの結合である。引数としてHListを受けとって、それをレシーバーであるHListの後ろに連結するメソッドとなる。
まずHNilは空のHListなので、これと何かのHListを結合するということは引数をそのまま返すことと同じになる。

func (this HNil[A]) Concat(hlist HList) HList {
	return hlist
}

次のHConsの場合は少しややこしい。HConsはリストと同じようにHeadとTailで構成されている。つまりHCons{head, tail}.Concat(hlist)というのは、Concatが後ろに連結するということからHCons{head, tail.Concat(hlist)}同じ結果となる。したがって次のように定義すればよい。

func (this HCons[H, T]) Concat(hlist HList) HList {
	return HCons[H, HList]{this.Head, this.Tail.Concat(hlist)}
}

このときTail.Concatを呼び出すために、HConsの型パラメーターTの型制約はanyではなくてHListとなっている。

すると次のように使うことができる。

func main() {
	hlist := HCons[int, HCons[bool, HCons[string, HNil[interface {}]]]]{
		1, 
		HCons[bool, HCons[string, HNil[interface {}]]]{
			true, 
			HCons[string, HNil[interface {}]]{
				"Hello",
				HNil[interface {}]{},
			},
		},
	}
	hlist2 := hlist.Concat(hlist)
	fmt.Printf(
		"HList value: %v\nLength: %v",
		hlist2,
		hlist2.Length(),
	)
}

HList value: {1 {true {Hello {1 {true {Hello {}}}}}}}
Length: 6

このように連結が成功していることがわかる。

まとめ

Cons[int]の最後にNil[bool]を入れてしまってもGetを定義する前に動いてしまったことには多少驚いたが、ちゃんと要素へアクセスする手段であるGetメソッドを用意すると無事にコンパイルエラーとなった。Go 2のGenericsは型推論が弱いので手動でやることが多いが、それなりに使える段階にあると思う。
また今回の記事では詳細に踏み込まなかったが、下記のドキュメントにはメソッド（レシーバーを持つ関数）が型パラメーターを利用できない理由が説明されている。

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

最初はこの型パラメーターを取るメソッドでもっと強力な型レベル計算をするつもりであったので、できないのは残念ではあるがドキュメントによるとそのような型パラメーターを取るメソッドを許可すると（型システム上はOKでも）ランタイムやコンパイル結果のバイナリー実行形式により前衛的な改造が必要となり、そのあたりのコンセンサスが困難になることから一旦削除したことが伺える。このようなランタイムへの影響と型システムのせめぎ合い（？）のようなものがあり興味深い。

脚注

1. プロポーザルには詳細な説明があるが、Genericsとはすごくシンプルに言えば「型の詳細を無視することでより汎用性の高いプログラムを作る」技術である。たとえばリストの長さを得るfunc Length() intのような関数があるとして、この関数はリストの内容の型がboolであってもstringであっても返り値などに何も影響しない。したがってこの型の詳細を無視しておくことで、1つのコードで複数の型に対して振る舞えるようになる（= 多相）というのが狙いである。この立場の下で型パラメーターに対する制約というのは、そこに入れることができる型を制限するのでむしろ型の詳細を「残す」方向へ作用する。したがってany（無制限）にしておくことが最もGenerics的な原理主義的かつ汎用性が高いコードとなることから、この記事がGenericsを解説することを目的としているその方向性に基づいて制約はあまり利用しないので、よってここでも細かい解説はせずなるべくanyを利用していく。

2. 現時点ではGo 2の型推論は相当適当であると思われるので、Cons[int]ような引数である1などから自明に推論できそうな型であってもプログラマーが手で与えていく必要がある。

3. ところどころにinterface {}が存在するが、これはHNilという終端の型に与えられた型パラメーターであり、HNilは値を持たない構造体であることから、このinterface {}は実際の値の型としては利用されない。したがってinterface {}な値が取り出されてキャストが生じるということはない。記事にはあまり関係ないが、このように値の型として利用されない型パラメーターは Phantom type と呼ばれる。