連結リストの実装でGo言語のジェネリクスのドラフトを触ってみる

James Kirk
Jul 7 · 13 min read
Image for post
Image for post
ジェネリクスの使いどころ(イメージ)

はじめに

Goの世界で最近話題になっているのが6月12日に発表されたジェネリクスのドラフトです。仕様がやや固まってきただけでなく、go2goで実際にコンパイルと実行することが可能になりました。
本記事では連結リストを実装しながらドラフトの仕様を見ていきます。全てのコードはサンプルレポジトリにあります。

7/15 UPDATE: 型パラメータのシンタックスで()の代わりに[]が使用される可能性があります。近いうちgo2goが更新され、両方使えるようになります。詳しくはGoogle Groupsまで。

8/21 UPDATE: []の使用が確定となりました。また、typeがなくなる代わりにConstraintが必須となります。Constraintがない場合はanyという新しい予約語を使います。詳しくはGoogle Groupsまで。

  • (type T Constraint)[T Constraint]
  • (type T)[T any]

10/9 UPDATE: 記事の内容を最新のシンタックスに更新しましまた。

ジェネリクスとは?

ジェネリクス(正式にはパラメータ多相)というのは型安全性を保ちながら様々な型に対応する汎用的な実装を可能にする手法です。コードの重複や実行時エラーを減らし、言語の表現力を高めることに繋がります。

Goの開発者は「シンプルさ」を大切にしているため、コミュニティの中にジェネリクスに対する懸念があります。ジェネリクスのWHYについてはThe Go BlogからのWhy Generics?を参考にしてください。

今回のドラフトについて

詳細は上記にありますが、要約すると以下の機能が提案されています。

  • 関数に型パラメータリストが定義できる: func F[T any](p T) { … }
  • どの型でも受け取る型パラメータを定義する時は、新しく導入される予約語anyを使う
  • 型に型パラメータリストが定義できる: type M[T any] []T
  • 各型パラメータに制限(Constraint)をインターフェイスで定義できる: func F[T Constraint](p T) { … }

以下の機能は仕様に含まれません。

go2goのセットアップ

go2goはドラフトのシンタックスを標準Goに変換するトランスパイラです。標準Goと同じようにローカルでソースからビルドもできますし、go2go Playgroundでも利用できます。ローカルで試してみたい方は以下の手順でソースからビルドしておきましょう。

// ディレクトリを作成
$ mkdir go2go
$ cd go2go
// ソースをクローン
$ git clone https://go.googlesource.com/go goroot
$ cd goroot
// 最新ブランチをチェックアウト
$ git fetch
$ git checkout dev.go2go
// ソースからビルド
$ cd src
$ ./make.bash

実行するには*.go2ファイルを作成しgo2go配下のツールを利用します。

// 環境変数をセット
$ export PATH="$HOME/go2go/goroot/bin:$PATH"
// .go2拡張子でGoのソースファイルを作成する
vim main.go2
// 実行する
$ go tool go2go run main.go2

連結リストの実装

構造体の定義

早速連結リストの実装に入りましょう。まずはどの型の値でも保持できる双方向ノードの構造体を定義します。型に制限がないため、anyをConstraintに使います。

type node[T any] struct {
value T // ジェネリックな値
prev *node[T] // 1つ前のnode
next *node[T] // 1つ後のnode
}

構造体の名前の直後に型パラメータリスト[]の中で定義します。型パラメータはフィールドやメソッドから参照できます。Tが具体的にどの型かはnodeを定義した時点では分かりません。nodeのインスタンスを生成する時に関数引数と同じように渡します。

型パラメータを複数定義する場合はコンマで区切ります。

type MultiParam[T any, U any] struct { … }

関数引数の型と同じように、連続で同じ型がある場合は省略できます。

type MultiParam[T, U any] struct { … }

nodeはエクスポートしないため、ラッパー構造体を定義します。

package listtype List[T any] struct {
head *node[T] // 最初のnode
last *node[T] // 最後のnode
}

func NewList[T any]() *List[T] {
return &List[T]{}
}

Listの型パラメータリストはnodeと同じですが、NewListでは関数名と引数リストの真ん中に置きます。以下のように生成します。

intList := list.NewList[int]()
stringList := list.NewList[string]()

関数引数からTの具体型が明らな場合、型推論で型パラメータの渡しを省略できますが、NewListに引数がないため明示的に渡す必要があります。構造体を直接生成する時も関数引数がないため同様です。

n := node{value: 1}      // 💀 コンパイルエラー
n := node[int]{value: 1} // ✅ コンパイルに成功

メソッドと関数の定義

Listの末尾に要素を追加できるようにAddLastメソッドを実装します。

func (l *List[T]) AddLast(item T) {
n := &node[T]{value: item}

if l.head == nil {
l.head = n
l.last = n
return
}

l.last.next = n
n.prev = l.last
l.last = n
}

*List[T]のようにレシーバ型に型パラメータリストをConstraintなしで追加し、引数リストや関数ボディから参照します。メソッドを更に追加してみましょう。

func (l *List[T]) AddFirst(item T) { }
func (l *List[T]) Print() { }

以下のように呼び出します。

intList.AddFirst(66)
intList.AddFirst(65)
intList.AddLast(67)
intList.Print() // [65, 66, 67]

stringList.AddFirst("B")
stringList.AddLast("C")
stringList.AddFirst("A")
stringList.Print() // [A, B, C]

FilterとMap

モダンな言語にはよく出てくるMapFilterFlatMapなどもジェネリクスで型安全な実装が可能です。まずはFilterを定義します。

func (l *List[T]) Filter(pred func(T) bool) *List[T] {
dest := NewList[T]()
for n := l.head; n != nil; n = n.next {
if pred(n.value) {
dest.AddLast(n.value)
}
}
return dest
}

func(T) boolのように第一級関数の引数リストからも型パラメータを参照でき、簡潔な実装になりました。以下のように呼び出します。

filterIntList := intList.Filter(func(i int) bool {
return i % 2 == 0
})
filterIntList.Print() // [66]

filterStringList := stringList.Filter(func(s string) bool {
return s > "A"
})
filterStringList.Print() // [B, C]

Mapの方はList[T]List[U]に変換する関数なので、型パラメータが2つ必要になります。本来は以下のように定義したいのですが、ドラフトの仕様だとメソッドに型パラメータを定義できません

// 💀 コンパイルしない
func
(l *List[T]) Map[U any](fn func(T) U) *List[U] { }

代わりにトップレベル関数として定義しないといけません。

func Map[T, U any](l *List[T], fn func(T) U) *List[U] {
dest := NewList[U]()
for n := l.head; n != nil; n = n.next {
value := fn(n.value)
dest.AddLast(value)
}
return dest
}

List[T]をインターフェイス化したい場合はハードルになりそうですが、このように呼び出せます。

intToString := list.Map(intList, func(i int) string {
return string(rune(i))
})
intToString.Print() // [A, B, C]

stringToInt := list.Map(stringList, func(s string) int {
return int(rune(s[0]))
})
stringToInt.Print() // [65, 66, 67]

コードサンプルFlatMapForEachなど他の関数の実装例もあります。

Constraintでリストを合計する

実装によっては受け取る型に制限をかけたい場合があります。例えば、整列リストだったら比較可能な型でないと要素をソートできません。これを実現するためにConstraintが提案されました。

型を明示的に指定する

Constraintはインターフェイスで定義します。制限をかけるにはtypeでどの型に対応するかを明示的に指定する方法があります。

type Ordered interface {
type int, int8, int16, int32, int64,
uint, uint8, uint16, uint32, uint64, uintptr,
float32, float64,
string
}

Orderedは比較可能な基本型の羅列です。OrderedをConstraintに使う場合、インターフェイス内にない型を渡すとコンパイルエラーになります。このような汎用的なConstraintがいくつか標準ライブラリに追加される可能性があります。

OrderedListの要素を合計する関数を書いてみましょう。

func SumOrdered[T Ordered](l *List[T]) T {
var sum T
for n := l.head; n != nil; n = n.next {
sum += n.value // 演算子+=が使える
}
return sum
}

T Orderedのように型パラメータ名のあとにConstraintを指定します。Orderedを満たす型を渡せば正常に合計が返却されます。

list.SumOrdered(intList)    // 198
list.SumOrdered(stringList) // ABC

挙動を指定する(通常のインターフェイス)

Orderedにない新しい型(Point)を定義しても、SumOrderedには渡せません。

type Point struct {
X, Y int
}
pointList := list.NewList(Point)()
pointList.AddLast(Point{1,1})
pointList.AddLast(Point{2,2})
pointList.AddLast(Point{3,3})
pointList.Print() // [{1 1}, {2 2}, {3 3}]
list.SumOrdered(pointList) // 💀 コンパイルエラー

Pointに対応するためにOrderedインターフェイスに型を追加するのではなく、足し算を可能にするメソッドをインターフェイスで定義します。

type Summable[T any] interface {
Add(t T) T
}
func Sum[T Summable[T]](l *List[T]) T {
var sum T
for n := l.head; n != nil; n = n.next {
sum = sum.Add(n.value) // メソッドを使う
}
return sum
}

指定する方法はOrderedと同じですが、今回はインターフェイスに定義したAddを使って合計します。この方法でSummableを実装した型すべてに対応できます。

// AddはSummableを満たせるメソッド
func (p Point) Add(q Point) Point {
return Point{
X: p.X + q.X,
Y: p.Y + q.Y,
}
}
list.Sum(pointList) // {6 6}

基本型とユーザー定義型の扱いが異なりますが、標準ライブラリにOrderedのようなConstraintsで基本型がだいたいカバーされるでしょう。

まとめ

今回はジェネリクスの新しいドラフトを紹介してgo2goでコードを実行しました。

実装してみた感想としては、Javaなど他の言語ほど機能は多くありませんが、高度な言語機能を「Goらしく」実現するためには適切なトレードオフなのではと思いました。他に思った点は以下になります。

  • 型パラメータリストの定義に()の代わりに[]を使う方がすっきりする
  • オートボクシングがないため基本型のパフォーマンスを活かせる
  • インターフェイスを使用するConstraintは自然に使える
  • interface{}に依存しないGoが楽しみになる

参考

Cover image by Jeff Potter

Eureka Engineering

Learn about Eureka’s engineering efforts, product…

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store