[インデックス 1962] ファイルの概要

このコミットは、Go言語の標準ライブラリにiterableパッケージを新しく追加し、container/vectorパッケージのVector型にDataメソッドを導入するものです。iterableパッケージは、All、Any、Mapといった、コレクションの要素を走査・変換するための便利な関数を提供します。これらの関数は、Goのチャネルとinterface{}を活用して、ジェネリックな操作を可能にしています。

コミット

commit 7b7785127552e1f9fd1a5b2b20f3de1ff1860f66
Author: David Symonds <dsymonds@golang.org>
Date:   Sun Apr 5 22:40:40 2009 -0700

    Add an Iterable package with handy functions like All, Any and Map.
    
    Add a Data method to vector.Vector.
    
    R=r,rsc
    APPROVED=rsc
    DELTA=173  (170 added, 0 deleted, 3 changed)
    OCL=26980
    CL=27098

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/7b7785127552e1f9fd1a5b2b20f3de1ff1860f66

元コミット内容

--- a/src/lib/container/Makefile
+++ b/src/lib/container/Makefile
@@ -36,8 +36,10 @@ O1=\
 
 O2=\
 \tintvector.$O\
+\titerable.$O\
 
 vector.a: a1 a2
+iterable.a: a1 a2
 
 a1:	$(O1)\
 	$(AR) grc vector.a vector.$O
@@ -45,19 +47,21 @@ a1:	$(O1)\
 
 a2:	$(O2)\
 	$(AR) grc vector.a intvector.$O\
+\t$(AR) grc iterable.a iterable.$O\
 	rm -f $(O2)\
 
 newpkg: clean
 	$(AR) grc vector.a\
+\t$(AR) grc iterable.a\
 
 $(O1): newpkg
 $(O2): a1
 
 nuke: clean
-\trm -f $(GOROOT)/pkg/vector.a\
+\trm -f $(GOROOT)/pkg/vector.a $(GOROOT)/pkg/iterable.a\
 
-packages: vector.a
+packages: vector.a iterable.a
 
 install: packages
 \tcp vector.a $(GOROOT)/pkg/vector.a
-\
+\tcp iterable.a $(GOROOT)/pkg/iterable.a
diff --git a/src/lib/container/iterable.go b/src/lib/container/iterable.go
new file mode 100644
index 0000000000..7963d14b57
--- /dev/null
+++ b/src/lib/container/iterable.go
@@ -0,0 +1,80 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// The iterable package provides several traversal and searching methods.
+// It can be used on anything that satisfies the Iterable interface,
+// including vector, though certain functions, such as Map, can also be used on
+// something that would produce an infinite amount of data.
+package iterable
+
+import "vector"
+
+
+type Iterable interface {
+	// Iter should return a fresh channel each time it is called.
+	Iter() <-chan interface {}
+}
+
+
+// All tests whether f is true for every element of iter.
+func All(iter Iterable, f func(e interface {}) bool) bool {
+	for e := range iter.Iter() {
+		if !f(e) {
+			return false
+		}
+	}
+	return true
+}
+
+
+// Any tests whether f is true for at least one element of iter.
+func Any(iter Iterable, f func(e interface {}) bool) bool {
+	return !All(iter, func(e interface {}) bool { return !f(e) });
+}
+
+
+// Data returns a slice containing the elements of iter.
+func Data(iter Iterable) []interface {} {
+	vec := vector.New(0);
+	for e := range iter.Iter() {
+		vec.Push(e)
+	}
+	return vec.Data()
+}
+
+
+// mappedIterable is a helper struct that implements Iterable, returned by Map.
+type mappedIterable struct {
+	it Iterable;
+	f func(interface {}) interface {};
+}
+
+
+func (m mappedIterable) iterate(out chan<- interface {}) {
+	for e := range m.it.Iter() {
+		out <- m.f(e)
+	}
+	close(out)
+}
+
+
+func (m mappedIterable) Iter() <-chan interface {} {
+	ch := make(chan interface {});
+	go m.iterate(ch);\
+	return ch;\
+}
+
+
+// Map returns an Iterable that returns the result of applying f to each
+// element of iter.
+func Map(iter Iterable, f func(e interface {}) interface {}) Iterable {
+	return mappedIterable{ iter, f }
+}
+
+
+// TODO:
+// - Find, Filter
+// - Inject
+// - Partition
+// - Zip
diff --git a/src/lib/container/iterable_test.go b/src/lib/container/iterable_test.go
new file mode 100644
index 0000000000..9c7d291105
--- /dev/null
+++ b/src/lib/container/iterable_test.go
@@ -0,0 +1,78 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package iterable
+
+import (
+	"iterable";
+	"testing";
+)
+
+type IntArray []int;
+
+func (arr IntArray) Iter() <-chan interface {} {
+	ch := make(chan interface {});
+	go func() {\
+		for i, x := range arr {\
+			ch <- x
+		}\
+		close(ch)\
+	}();\
+	return ch\
+}
+
+var oneToFive IntArray = []int{ 1, 2, 3, 4, 5 };
+
+func isNegative(n interface {}) bool {
+	return n.(int) < 0
+}
+func isPositive(n interface {}) bool {
+	return n.(int) > 0
+}
+func isAbove3(n interface {}) bool {
+	return n.(int) > 3
+}
+func isEven(n interface {}) bool {
+	return n.(int) % 2 == 0
+}
+func doubler(n interface {}) interface {} {
+	return n.(int) * 2
+}
+func addOne(n interface {}) interface {} {
+	return n.(int) + 1
+}
+
+
+func TestAll(t *testing.T) {
+	if !All(oneToFive, isPositive) {
+		t.Error("All(oneToFive, isPositive) == false")
+	}
+	if All(oneToFive, isAbove3) {
+		t.Error("All(oneToFive, isAbove3) == true")
+	}
+}
+
+
+func TestAny(t *testing.T) {
+	if Any(oneToFive, isNegative) {
+		t.Error("Any(oneToFive, isNegative) == true")
+	}
+	if !Any(oneToFive, isEven) {
+		t.Error("Any(oneToFive, isEven) == false")
+	}
+}
+
+
+func TestMap(t *testing.T) {
+	res := Data(Map(Map(oneToFive, doubler), addOne));
+	if len(res) != len(oneToFive) {
+		t.Fatal("len(res) = %v, want %v", len(res), len(oneToFive))
+	}
+	expected := []int{ 3, 5, 7, 9, 11 };
+	for i := range res {
+		if res[i].(int) != expected[i] {
+			t.Errorf("res[%v] = %v, want %v", i, res[i], expected[i])
+		}
+	}
+}
diff --git a/src/lib/container/vector.go b/src/lib/container/vector.go
index 07c7d3df0b..392e5e596d 100644
--- a/src/lib/container/vector.go
+++ b/src/lib/container/vector.go
@@ -107,6 +107,16 @@ func (p *Vector) Last() Element {
 }
 
 
+// Data returns all the elements as a slice.
+func (p *Vector) Data() []Element {
+	arr := make([]Element, p.Len());
+	for i, v := range p.a {
+		arr[i] = v
+	}
+	return arr
+}
+
+
 // Insert inserts into the vector an element of value x before
 // the current element at index i.\
 func (p *Vector) Insert(i int, x Element) {

変更の背景

このコミットが行われた2009年4月は、Go言語がまだ公開されて間もない、非常に初期の段階でした。当時のGoには、現在のようなジェネリクス（型パラメータ）の機能は存在しませんでした。そのため、異なる型を扱う汎用的なデータ構造やアルゴリズムを実装する際には、interface{}型（任意の型を受け入れることができる空のインターフェース）と型アサーションを駆使する必要がありました。

このような背景の中、コレクション（この場合はcontainer/vectorパッケージのVector型）の要素を効率的に走査したり、変換したりする共通のパターンが求められていました。特に、関数型プログラミングのパラダイムでよく見られるMap、All、Anyといった高階関数は、コードの記述を簡潔にし、再利用性を高める上で非常に有用です。

このコミットの目的は、Go言語の初期の制約（ジェネリクス不在）の中で、チャネルとinterface{}を組み合わせることで、汎用的なイテレーション機能とコレクション操作機能を提供することにありました。また、vector.Vectorが内部のデータをスライスとして簡単に公開できるようにすることで、他のGoの機能との連携を容易にすることも意図されています。

前提知識の解説

このコミットの技術的詳細を理解するためには、以下のGo言語の初期の概念とプログラミングパラダイムに関する知識が必要です。

1. Go言語の初期の設計思想とジェネリクス不在

Go言語は、シンプルさ、効率性、並行処理の容易さを重視して設計されました。しかし、初期のバージョンでは、C++のテンプレートやJavaのジェネリクスのような型パラメータの機能は意図的に導入されませんでした。これは、コンパイル時間の短縮、コードの複雑性の抑制、そして型推論のシンプルさを保つためでした。

この設計上の選択により、異なる型を扱う汎用的なデータ構造（例: リスト、マップ）を実装する際には、interface{}型を使用し、実行時に型アサーションを行う必要がありました。これにより、型安全性が損なわれる可能性や、パフォーマンスのオーバーヘッドが生じるというトレードオフがありました。

2. `interface{}` と型アサーション

interface{}は、Go言語における「空のインターフェース」であり、いかなる型もinterface{}型として扱うことができます。これは、Goにおけるポリモーフィズムの最も基本的な形です。

var i interface{}
i = 42       // int型をinterface{}に代入
i = "hello"  // string型をinterface{}に代入

interface{}型の値を元の具体的な型に戻すには、型アサーションを使用します。

var i interface{} = 42
j := i.(int) // iをint型としてアサート
s := i.(string) // パニック発生（iはint型なのでstring型ではない）

このコミットでは、interface{}を多用することで、ジェネリクスがない環境下で汎用的なコレクション操作を実現しています。

3. `chan` (チャネル) の基本的な使い方とイテレータパターンへの応用

Go言語のチャネルは、ゴルーチン間で値を送受信するためのパイプのようなものです。チャネルは並行処理の同期と通信の主要なメカニズムであり、Goの大きな特徴の一つです。

チャネルの作成: ch := make(chan Type)
値の送信: ch <- value
値の受信: value := <-ch
チャネルのクローズ: close(ch)

チャネルは、イテレータパターンを実装するための強力なツールとしても利用できます。あるゴルーチンがチャネルにデータを送信し、別のゴルーチンがそのチャネルからデータを受信することで、コレクションの要素を順次処理するような振る舞いを実現できます。for ... rangeループはチャネルに対しても使用でき、チャネルがクローズされるまで値を受信し続けます。

func generateNumbers() <-chan int {
    ch := make(chan int)
    go func() {
        for i := 0; i < 5; i++ {
            ch <- i
        }
        close(ch)
    }()
    return ch
}

func main() {
    for num := range generateNumbers() {
        fmt.Println(num)
    }
}

このコミットでは、IterableインターフェースのIter()メソッドが<-chan interface{}（受信専用チャネル）を返すことで、このチャネルベースのイテレータパターンを採用しています。

4. `container/vector` パッケージの役割

container/vectorパッケージは、Go言語の初期の標準ライブラリに含まれていた、動的な配列（ベクター）を実装するパッケージです。これは、C++のstd::vectorやJavaのArrayListに相当するもので、要素の追加、削除、アクセスなどの基本的な操作を提供します。

ジェネリクスがないため、vector.Vectorはinterface{}型の要素を格納するように設計されていました。

5. 関数型プログラミングの概念（`Map`, `All`, `Any`など）

関数型プログラミングは、計算を関数の評価として捉えるプログラミングパラダイムです。このコミットで導入されるAll、Any、Mapは、関数型プログラミングでよく使われる高階関数（関数を引数として受け取ったり、関数を返したりする関数）の例です。

Map: コレクションの各要素に関数を適用し、その結果を新しいコレクションとして返します。
All: コレクションのすべての要素が特定の条件を満たすかどうかをテストします。
Any: コレクションの少なくとも1つの要素が特定の条件を満たすかどうかをテストします。

これらの関数は、ループを直接記述する代わりに、より抽象的で宣言的な方法でデータ変換や検証を行うことを可能にします。

技術的詳細

このコミットは、Go言語の初期におけるジェネリクス不在の課題に対し、interface{}とチャネルを巧みに利用して汎用的なコレクション操作機能を提供するものです。

1. `iterable` パッケージの導入

iterableパッケージは、コレクションの走査と変換のための共通インターフェースと関数を提供します。

`Iterable` インターフェース

type Iterable interface {
	// Iter should return a fresh channel each time it is called.
	Iter() <-chan interface {}
}

このインターフェースは、Iter()メソッドを定義しています。このメソッドは、interface{}型の値を送信する受信専用チャネルを返します。これにより、Iterableインターフェースを実装する任意の型は、その要素をチャネルを通じて順次提供できるようになります。Iter()が呼び出されるたびに新しいチャネルを返すという要件は、複数のイテレーションが独立して行われることを保証するために重要です。

`All` 関数

func All(iter Iterable, f func(e interface {}) bool) bool {
	for e := range iter.Iter() {
		if !f(e) {
			return false
		}
	}
	return true
}

All関数は、Iterableのすべての要素が与えられた述語関数fを満たすかどうかをテストします。要素が1つでもfを満たさない場合、即座にfalseを返します。すべての要素がfを満たせばtrueを返します。

`Any` 関数

func Any(iter Iterable, f func(e interface {}) bool) bool {
	return !All(iter, func(e interface {}) bool { return !f(e) });
}

Any関数は、Iterableの少なくとも1つの要素が与えられた述語関数fを満たすかどうかをテストします。これは、All関数を否定の述語で呼び出すことで簡潔に実装されています。つまり、「すべての要素がfを満たさないわけではない」という論理で「いずれかの要素がfを満たす」ことを表現しています。

`Data` 関数

func Data(iter Iterable) []interface {} {
	vec := vector.New(0);
	for e := range iter.Iter() {
		vec.Push(e)
	}
	return vec.Data()
}

Data関数は、Iterableのすべての要素を[]interface{}型のスライスとして返します。内部的には、vector.Vectorのインスタンスを一時的に使用して要素を収集し、最終的にvector.VectorのData()メソッド（このコミットで追加される）を呼び出してスライスを取得しています。

`Map` 関数と `mappedIterable`

type mappedIterable struct {
	it Iterable;
	f func(interface {}) interface {};
}

func (m mappedIterable) iterate(out chan<- interface {}) {
	for e := range m.it.Iter() {
		out <- m.f(e)
	}
	close(out)
}

func (m mappedIterable) Iter() <-chan interface {} {
	ch := make(chan interface {});
	go m.iterate(ch);\
	return ch;\
}

func Map(iter Iterable, f func(e interface {}) interface {}) Iterable {
	return mappedIterable{ iter, f }
}

Map関数は、Iterableの各要素に変換関数fを適用した結果を返す新しいIterableを生成します。この機能は、mappedIterableという内部構造体によって実現されています。 mappedIterableは、元のIterableと変換関数fを保持します。そのIter()メソッドは、新しいチャネルを作成し、別のゴルーチンで元のIterableから要素を読み込み、fを適用した結果を新しいチャネルに送信します。これにより、遅延評価（lazy evaluation）のような振る舞いが可能になり、無限のデータストリームに対してもMapを適用できます。

2. `container/vector.go` への `Data()` メソッドの追加

func (p *Vector) Data() []Element {
	arr := make([]Element, p.Len());
	for i, v := range p.a {
		arr[i] = v
	}
	return arr
}

vector.Vector型にData()メソッドが追加されました。このメソッドは、Vectorが内部に保持するすべての要素を[]Element（Elementはinterface{}のエイリアス）型のスライスとして返します。これにより、Vectorの内部データへのアクセスが容易になり、iterable.Data関数のような外部の関数がVectorの要素をスライスとして取得できるようになります。

3. `Makefile` の変更

src/lib/container/Makefileが更新され、新しく追加されたiterableパッケージがビルドおよびインストールされるように変更されました。具体的には、iterable.oがビルド対象に追加され、iterable.a（アーカイブファイル）が作成され、GOROOT/pkg/ディレクトリにコピーされるようになっています。これにより、iterableパッケージがGoの標準ライブラリの一部として利用可能になります。

4. テストコード (`iterable_test.go`)

新しく追加されたiterable_test.goは、iterableパッケージの機能が正しく動作することを検証します。

IntArray型とIter()メソッドの実装: テストのために、[]intをラップしたIntArray型が定義され、Iterableインターフェースを実装しています。これにより、具体的な数値スライスを使ってiterableパッケージの関数をテストできます。
述語関数と変換関数: isNegative, isPositive, isAbove3, isEvenといった述語関数や、doubler, addOneといった変換関数が定義され、テストケースで使用されています。
TestAll: All関数が正しく動作するか（すべての要素が条件を満たす場合と満たさない場合）をテストします。
TestAny: Any関数が正しく動作するか（いずれかの要素が条件を満たす場合と満たさない場合）をテストします。
TestMap: Map関数が正しく要素を変換し、その結果が期待通りになるかをテストします。特に、Mapを複数回適用した結果も検証しています。

これらのテストは、iterableパッケージが提供する機能の基本的な動作と、interface{}とチャネルを使ったイテレータパターンの有効性を確認しています。

コアとなるコードの変更箇所

このコミットのコアとなるコードの変更箇所は以下のファイルとセクションです。

src/lib/container/iterable.go: このファイル全体が新規追加されており、Iterableインターフェースの定義と、All, Any, Data, Mapといった主要なイテレーション関数が実装されています。特に、チャネルを用いたイテレータパターンとmappedIterableによるMapの実装が重要です。

src/lib/container/vector.go: Vector型に新しく追加されたData()メソッド。

// Data returns all the elements as a slice.
func (p *Vector) Data() []Element {
	arr := make([]Element, p.Len());
	for i, v := range p.a {
		arr[i] = v
	}
	return arr
}

src/lib/container/Makefile: iterableパッケージのビルドとインストールに関する変更。

--- a/src/lib/container/Makefile
+++ b/src/lib/container/Makefile
@@ -36,8 +36,10 @@ O1=\
 
 O2=\
 \tintvector.$O\
+\titerable.$O\
 
 vector.a: a1 a2
+\titerable.a: a1 a2
 
 a1:	$(O1)\
 	$(AR) grc vector.a vector.$O
@@ -45,19 +47,21 @@ a1:	$(O1)\
 
 a2:	$(O2)\
 	$(AR) grc vector.a intvector.$O\
+\t$(AR) grc iterable.a iterable.$O\
 	rm -f $(O2)\
 
 newpkg: clean
 	$(AR) grc vector.a\
+\t$(AR) grc iterable.a\
 
 $(O1): newpkg
 $(O2): a1
 
 nuke: clean
-\trm -f $(GOROOT)/pkg/vector.a\
+\trm -f $(GOROOT)/pkg/vector.a $(GOROOT)/pkg/iterable.a\
 
-packages: vector.a
+\tpackages: vector.a iterable.a
 
 install: packages
 \tcp vector.a $(GOROOT)/pkg/vector.a
-\
+\tcp iterable.a $(GOROOT)/pkg/iterable.a

コアとなるコードの解説

`src/lib/container/iterable.go`

このファイルは、Go言語におけるイテレータパターンと高階関数を、ジェネリクスがない初期のGoの制約下でどのように実現したかを示す典型的な例です。

Iterable インターフェース: Iter() <-chan interface{}というメソッドシグネチャが鍵です。これは、イテレータがチャネルを通じて要素をストリームとして提供するというGoらしいアプローチを示しています。interface{}を使用することで、任意の型の要素を扱う汎用性を確保しています。<-chanは受信専用チャネルであることを示し、イテレータの利用側がチャネルに値を送信することを防ぎ、データの流れを明確にしています。
All, Any 関数: これらの関数は、Iterableインターフェースを通じて提供される要素ストリームを消費し、述語関数fに基づいて論理的な判断を行います。for e := range iter.Iter()というイディオムは、チャネルがクローズされるまで要素を効率的に処理するGoの標準的な方法です。AnyがAllの否定として実装されているのは、コードの再利用と簡潔さの良い例です。
Data 関数: Data関数は、イテレータからすべての要素を読み込み、それらを[]interface{}スライスに変換します。内部でvector.New(0)とvec.Push(e)を使用しているのは、当時のGoの標準ライブラリで動的なスライス構築を支援するcontainer/vectorが利用可能だったためです。最終的にvec.Data()を呼び出すことで、Vectorの内部スライスを取得しています。
Map 関数と mappedIterable: Map関数は、関数型プログラミングの重要な概念である「マップ」操作を実装しています。注目すべきは、mappedIterableという構造体と、そのIter()メソッドの実装です。 mappedIterableは、元のIterableと変換関数fを保持します。 mappedIterable.Iter()メソッドは、新しいチャネルを作成し、go m.iterate(ch)によって別のゴルーチンでm.iterate関数を実行します。m.iterateは、元のイテレータから要素を読み込み、m.f（変換関数）を適用した結果を新しいチャネルに送信します。最後にclose(out)でチャネルをクローズします。この設計により、Map操作は「遅延評価」されます。つまり、実際に要素が要求されるまで変換処理は行われません。これは、無限のストリームに対してもMapを適用できるという利点があります。

`src/lib/container/vector.go` の `Data()` メソッド

Data()メソッドは、vector.Vectorの内部表現（p.aというスライス）を直接コピーして新しいスライスとして返します。

func (p *Vector) Data() []Element {
	arr := make([]Element, p.Len()); // Vectorの現在の長さと同じ容量のスライスを作成
	for i, v := range p.a {          // 内部スライスp.aの要素をループ
		arr[i] = v                   // 新しいスライスにコピー
	}
	return arr                       // コピーされたスライスを返す
}

このメソッドは、Vectorの要素をGoの組み込みスライスとして簡単に利用できるようにするために追加されました。これにより、iterable.Data関数がVectorの要素を効率的に取得できるようになります。

`src/lib/container/Makefile`

Makefileの変更は、Goのビルドシステムがどのように新しいパッケージを認識し、コンパイルしてインストールするかを示しています。

O2変数にiterable.$O（iterable.goのコンパイル済みオブジェクトファイル）が追加され、ビルド対象となることを示しています。
iterable.a: a1 a2という行は、iterable.aというアーカイブファイル（Goパッケージのコンパイル済みバイナリ）がa1とa2というターゲットに依存することを示しています。
a2ターゲット内で$(AR) grc iterable.a iterable.$Oが実行され、iterable.oがiterable.aにアーカイブされます。
newpkgターゲットとnukeターゲットにもiterable.aが追加され、クリーンアップや新規パッケージ作成時に適切に扱われるようにしています。
packagesターゲットにiterable.aが追加され、installターゲットでcp iterable.a $(GOROOT)/pkg/iterable.aが実行されることで、iterable.aがGoの標準パッケージディレクトリにコピーされ、他のGoプログラムからimport "iterable"として利用可能になります。

これらの変更は、Goの初期のビルドプロセスがMakefileベースであったことを示しており、新しいパッケージを追加する際には手動でMakefileを更新する必要があったことがわかります。

参考にした情報源リンク

Go言語の公式ドキュメント (当時のバージョンに関する情報を見つけるのは難しいですが、基本的な概念は共通です)
Go言語のソースコードリポジトリ (コミット履歴とファイル内容から直接情報を取得)
Go言語の歴史に関するブログ記事やフォーラムの議論 (ジェネリクス不在の時代におけるGoの設計上の選択について)
関数型プログラミングの概念に関する一般的な情報源 (Map, All, Anyなどの高階関数について)
Go language design FAQ - Why no generics? (Go 1.18以前のジェネリクスに関する公式見解)
Go's Concurrency Primitives: Channels (チャネルの基本的な使い方とパターンに関する公式ブログ記事)# [インデックス 1962] ファイルの概要