コレクション、イテレータ、そして inject のパワー

JavaScript

注: これは Ruby のコードではありません (笑):

var ibm = [ 'H', 'A', 'L' ].inject('', function (str, item)
{
    return str + item.succ();
});
print(ibm); // -> 'IBM'

いきなり結果からお見せしましたが、今回は難しいと言われている inject メソッドの習得を目指しつつ、JavaScript における「コレクション」と「コレクション・メソッド」への理解を深めていきたいと思います。

コレクション、コレクション・メソッド

コレクションとは、配列や連想配列、リンク・リストなど、オブジェクトの集合を表したものです。コンテナとも言います。

コレクション・メソッドとは、コレクションの要素へのアクセスを提供するメソッドのことで、イテレータと呼ぶこともあります*1。したがって、この文脈で「コレクション」と言う場合、単なる集合ではなく、集合要素へのアクセスを (メソッドとして) 提供しているオブジェクト、ということになります。

実は、JavaScript には本来このようなメソッドは備わっていません (でした)*2。

ですが、

  • 組み込みクラスに対して容易にメソッドを追加できる
  • 関数の引数に関数を受け取れる

この二つの特性により、冒頭の例のようなことが実現可能になるのです。

コレクションへのアクセスを実現する仕組み: each メソッドと Enumerable モジュール

イテレータ (= コレクション・メソッド) の基本は要素へのアクセスを提供することですから、配列であれば for か while ループを使って実装することになります。このループの中で (毎回) 外部と関連付けられたメソッドを実行する、ということが即ち「アクセスを提供する」ことになるわけです。

Ruby は、コレクションのタイプ毎に "each" という一つのイテレータを実装するだけで、検索、加工など多数のイテレータを利用できるようになる、という素晴らしい仕組みを持っています:

"each" という共通のインターフェースに依拠して (つまり、コレクションのタイプとは無関係に) 多種多様なイテレータを実装している Enumerable というモジュールがあり、これをコレクション・クラスに組み込む (Mixin)、というものです。

prototype.js も、これと全く同じモデルを採っています。

説明のために、任意のオブジェクトの「範囲」を表現する Range というコレクション・クラスを実装してみましょう。prototype.js の ObjectRange をより汎用的に利用できるよう書き換えたものです*3:

var Range = Class.create(
{
    initialize: function (from, upto, exclusive)
    {
	this.mixin(Enumerable);
	this.from = from;
	this.upto = upto;
	this.exclusive = exclusive;
    },
    _each: function (yield)
    {
	for (var i = this.from; this.include(i); i = i.succ())
	{
	    yield(i);
	    if (this._eq(i, this.upto))
		/* NOTE: 例えば ('a' .. 'z') の範囲とします。
		 * 'z'.succ() は 'aa' を生じますが、これは 'z' より小さいと見な
		 * されるため、include() は真を返します: ループが範囲を超えて回
		 * ってしまうわけです。
		 *
		 * Ruby においても
		 * ('a'..'z').include? 'aa'
		 * は真となります (1.8.4 でテストしました。これがバグと見なすべ
		 * き問題なのかどうかは私には分かりません)。
		 * ループの場合これはまずいので、ここで break します。
		 */
		break;
	}
    },
    include: function (value)
    {
	return this._le(this.from, value) &&
				(this.exclusive ? this._lt(value, this.upto)
						: this._le(value, this.upto));
    },
    _eq: function (a, b)
    {
	return (a == b) || (a.toString() == b.toString());
    },
    _le: function (a, b)
    {
	return this._eq(a, b) || this._lt(a, b);
    },
    _lt: function (a, b)
    {
	return (a < b) || (a.toString() < b.toString());
    }
});

これで、Enumerable が提供する全てのイテレータが利用できるようになります。

でもまずは、全ての基本となる each の用法から見ていきましょう。例は 1 から 10 のうち、奇数を配列として取得するものです:

// 配列の宣言
var a = [];
// イテレータを用いた配列の操作
(new Range(1, 10)).each(function (item)
{
    if (item % 2)
      a.push(item);
});

イテレータに対して、実行して欲しいことを関数として渡します*4。組み込みの関数でも何でも構いません。この関数は 1 から 10 までの値を順に一つずつ受け取り、それを用いて自由に操作を行う機会を与えられるわけです。

これ自体、相当便利なものと言えます。

が、Enumerable の中に「条件に合致するものだけを配列として返す」ためのメソッドが既に用意されていました。これを使うと、同じことが一文で書けるようになります:

// 配列の定義
var a = (new Range(1, 10)).findAll(function (item)
{
    return item % 2;
});

このように、目的に合ったメソッドが既にあるかどうかを知る、ということがイテレータを使いこなす上で重要になってくると言えるでしょう。

inject メソッド

inject は Smalltalk やバージョン 1.7 以降の Ruby でサポートされているイテレータです。prototype.js ではバージョン 1.4.0 pre1 から Enumerable と共にサポートされています。

「注入」という意味ですが、あらゆるコレクションの要素を自由に加算・蓄積、取捨することを可能にする、非常に強力なメソッドです。

inject の実装については Prototype のソースを見ていただくとして、ここでは使い方のパターンを把握することに努めましょう (紙を無駄にしないよう気をつけてください)。

数値に inject
var accum = (new Range(1, 10)).inject(0, function (num, item)
{
    return num + item;
});
print(accum); // -> 55
文字列に inject
var accum = (new Range('a', 'z')).inject('The alphabet: ', function (str, item)
{
    return str + item;
});
print(accum); // -> "The alphabet: abcdefghijklmnopqrstuvwxyz"
配列に inject
var accum = (new Range('c', 'z')).inject(['A','B'], function (arr, item)
{
    arr.push(item.toUpperCase());
    return arr;
});
print(accum.join(""));  // -> "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
オブジェクト (連想配列) に inject
var accum = (new Range('a', 'z')).inject({}, function (obj, item)
{
    obj[item] = item.charCodeAt(0);
    return obj;
});
print(accum.u); // -> 117

初期値 (inject の第一引数) と戻り値のデータ・タイプが同じになる、というのがポイントです。つまり、結果として数値が欲しければ数値、配列が欲しければ配列、自分で定義したクラスでも構いません、その初期状態を、inject に渡してやれば良いわけです。

すると、その初期値は最初のコレクション要素と共に、それぞれ第一、第二引数として関数*5に渡されます。

この関数内で、それらの値に加算等の処理を行い、第一引数の方を return してやります。そうすると、次のループでは初期値のちょっと成長したものがやって来ることになります。

これが繰り返され、初期値がどんどん大きくなっていくわけです*6。


従来、単純にループを回して同様の処理をしていたことを考えると、ちょっと思考の転換が必要とされるのではないかと思います。しかし、慣れれば非常に便利に使えるメソッドです。Prototype の Enumerable メソッド自体にも inject を使ってより簡潔に書き換えられるものが結構ありますので、練習のためにリファクターしてみるのも良いんじゃないでしょうか？


最後に、文字クラスの succ() メソッドの実装 (Ruby の C レベルの実装を真似て、その後単純化したもの) です:

String.prototype.succ = function ()
{
    // Trying to mimic ruby's logic (string.c: rb_str_succ)
    var str = this;	// take a copy
    var car = null;	// remember what to "carry"
    var pos = str.length - 1;

    function succ(p, force)
    {
	var c = str.charAt(p);
	if (force ||
		(c >= '0' && c < '9') ||
		(c >= 'a' && c < 'z') ||
		(c >= 'A' && c < 'Z'))
	    return set(p, String.fromCharCode(c.charCodeAt(0)+1));
	else if (c == '9')
	{
	    car = '1';
	    set(p, '0');
	}
	else if (c == 'z')
	    set(p, (car = 'a'));
	else if (c == 'Z')
	    set(p, (car = 'A'));
	else if (car)
	    return set(p, car, true);
	else if (p < 0)
	    return false;
	// Either no alnum found or needs to carry
	return succ(--p);
    }

    function set(p, c, ins)
    {
	var f = p + (ins ? 1 : 0);
	var l = p + 1;
	return (str = str.slice(0, f) + c + str.slice(l));
    }

    return succ(pos) || succ(pos, true);
};

JScript でしか試していませんが、'<>'.succ() が '<>' になれば成功です。


参考文献:
Martin Fowler. CollectionClosureMethod.
Dave Thomas and Andy Hunt. Programming Ruby.
oleg at pobox dot com. Towards the best collection API.

*1:イテレータがオブジェクトとして実装される場合にはもちろんこの表現は当てはまらないでしょう

*2:現在の Mozilla の実装では幾つかの配列イテレータをサポートしていますが、ここでは取り上げません

*3:「任意の」クラスがこれを利用するためには、適切な succ および toString メソッドを定義している必要があります (Enumerable に対する each の関係と同じことです)。文字クラスの succ メソッドは最後に示してあります

*4:Ruby 等の界隈で「イテレータ」という言葉を「クロージャ」の意味で使ったりする人をよく見かけますが、英語の意味を理解すれば直ちにこの混同は無くなるでしょう。"iterate" は「繰り返す・反復する」。for や while ループをイメージしてください。これをオブジェクトまたはメソッドとして抽象化したものがイテレータです。一方クロージャには「繰り返し」の意味はありません。外のスコープにある変数を中に閉じ込める = "close in" というところから来ており、そのような性質を持つ関数ないしはコード・ブロックのことを言います

*5:この、イテレータに渡される関数のことを "iteratee" と呼ぶ人もいます。が、この言葉を「イテレートされる側」、即ちコレクションの意味で使う人も多く、混乱が存在しています。また、Prototype のソースにおいてはこれを "iterator" という誤った引数名で受け取っています

*6:値を蓄積せず、常に一つの値を選択するような使い方も出来ます (例: 最小値の検出) ので、この説明は必ずしも適切ではないかも知れません