Open in app

Sign in

Write

Sign in

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

James Kirk
Eureka Engineering
Published in
14 min readJul 7, 2020
ジェネリクスの使いどころ（イメージ）

この記事はアーカイブ済みです

この記事はGo 1.18のリリース前に書かれたものです。Go 1.18以降のジェネリクスについて是非以下の記事を参照してください。

Abstracting database/sql boilerplate with Go generics

Exploring what can be achieved using Go generics with no added dependencies

medium.com

Tutorial: Getting started with generics - The Go Programming Language

This tutorial introduces the basics of generics in Go. With generics, you can declare and use functions or types that…

go.dev

An Introduction To Generics - The Go Programming Language

Robert Griesemer and Ian Lance Taylor 22 March 2022 This blog post is based on our talk at GopherCon 2021: The Go 1.18…

go.dev

はじめに

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

Jimeux/go-samples/generics-design-draft

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

github.com

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

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

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

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

2021/2/11 UPDATE: ドラフトが正式に承認されました。

ジェネリクスとは？

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

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

今回のドラフトについて

Type Parameters - Draft Design

Ian Lance TaylorRobert GriesemerJune 16, 2020 We suggest extending the Go language to add optional type parameters to…

go.googlesource.com

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

  • 関数に型パラメータリストが定義できる： 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でも利用できます。ローカルで試してみたい方は以下の手順でソースからビルドしておきましょう。

dev.go2go branch

This branch contains a type checker and a translation tool for experimentation with generics in Go. This implements the…

go.googlesource.com

// ディレクトリを作成
$ 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] // １つ前のnode
   next *node[T] // １つ後の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

モダンな言語にはよく出てくるMap、Filter、FlatMapなどもジェネリクスで型安全な実装が可能です。まずは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]に変換する関数なので、型パラメータが２つ必要になります。本来は以下のように定義したいのですが、ドラフトの仕様だとメソッドに型パラメータを定義できません。

// 💀 コンパイルしない
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]

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

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がいくつか標準ライブラリに追加される可能性があります。

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

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

Go
Generics
Golang
Data Structures
Programming

--

--

James Kirk
Eureka Engineering

Written by James Kirk

205 Followers
Editor for

Back-end engineer and gopher at Eureka.

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams