generator
ActionScript3でPythonっぽい(?)外部イテレータを利用する話です。既出だったらどうしよう。。
http://www.be-interactive.org/index.php?itemid=40
http://www.be-interactive.org/?itemid=39
数年前、ActionScript神がRubyのEnumerableをASでやっていました。eachメソッドさえ実装すれば、様々な便利メソッドがミクシンで使えるようになるというものです。その後AS3になり、Array#mapとか標準で使えるようにはなったのですが、クロージャに要求する引数の数が多くてちょっと使いにくいと思います。
そこで以下のような反復処理ライブラリをやってみたくなるわけです。
- Python的な外部イテレータで無限リストとか扱えるようにしてみよう。
- 神に習って反復をbreakする方法を提供しよう。
- 大クラス主義で作ってメソッドチェインを促進しよう。
まず、ジェネレータの扱いですが、Flashにはyieldというか、継続のようなものがないため本来なら以下のように書けるようにしたいところを、
function generator() {
yield(0);
yield(1);
yield(2);
}
以下のように書くことにします。
function generator():Function {
var i:uint = 0;
return function():Number {
if (i < 3) return i++;
Iterable.stop(); //反復から脱出
return undefined; //ここは実行されないが、コンパイラに怒られないために書く
}
}
「次の要素を返す関数」を返す関数をジェネレータってことにしてしまいます。反復のbreakに相当するのがIterable.stop()で、要素を順番に取り出していき後がなくなったときにStopIterationという例外を起こします。
var next:Function = generator(); trace(next()); // => 0 trace(next()); // => 1 trace(next()); // => 2 trace(next()); // => Error: StopIteration
そうするとeachのモックは以下のように、StopIteration例外が起きるまで値を取り出して、callback関数に処理してもらう感じになります。
function each(generator:Function, callback:Function):void {
var next:Function = generator();
while(true) {
try {
callback(next());
} catch (e:StopIteration) {
break;
}
}
}
each(generator, trace);
/* =>
0
1
2
*/
今回提案するライブラリでは、このような関数的な書き方ではなく、以下のように書けるようにしてみました。
iter(generator).each(trace);
iter関数は、Functionだけではなく様々な型を受け付けてIterableインスタンスを返し、こいつにeachを始めとする多くの反復系メソッドを実装してあります。例えば以下では、配列からIterableを作り、正規表現でフィルタして再び配列に戻します。
iter(['one', 'two', 'three']).grep(/o/).toArray(); // => ['one', 'two']
Objectを渡した場合、値の配列として扱われます。以下の例では合計を求めています。foldは畳み込み関数です。
iter({a:1, b:2, c:3}).fold(0, function(a:Number, b:Number):Number {
return a + b;
}); // => 6
自作のコンテナクラスを反復に対応させる場合などは、generatorという名前のメソッドをあらかじめ定義しておきます。以下では、0〜1の無限の乱数列を-1〜1にマップして、始めから10要素を取り出してtraceしています。
iter({generator:function():Function {
return function():Number {
return Math.random();
};
}}).map(function(n:Number):Number {
return n * 2 - 1;
}).slice(10).each(trace);
ここでslice(10)しないと、eachで永遠に要素を辿ろうとしてしまうので注意です。mapは、その場で無限リストを処理しているのではなく、元のジェネレータ関数をラップした新しいIterableを返します。以下のようなイメージです。
var 元のジェネレータ:Function = function():Function {
return function():Number {
return Math.random();
}
}
var マップ後のジェネレータ:Function = function():Function {
var next:Function = 元のジェネレータ();
return function():Number {
return next() * 2 - 1;
}
}
一方のeachは、mapと違い処理を先送りにはできませんから、無限リストに対して呼び出すとまずいわけです。
この他にも便利と思われるメソッドを大量に詰め込んだものの、全てを解説する気力がないので続きはソースということで・・
//iter.as
package {
public function iter(iterable:*):Iterable {
return Iterable.iter(iterable);
}
}
//Iterable.as
package {
public class Iterable {
/*
ArrayやObject、ジェネレータ関数から反復可能なオブジェクトを新しく返します
*/
public static function iter(it:*):Iterable {
if (it is Iterable)
return Iterable(it);
return new Iterable(makeGenerator(it));
}
/*
startから始まる整数列を返します
*/
public static function count(start:uint = 0):Iterable {
return new Iterable(function():Function {
var i:uint = start;
return function():uint {
return i++;
};
});
}
/*
有限列を繰り返した無限列を返します
*/
public static function cycle(iterable:*):Iterable {
return new Iterable(function():Function {
var next:Function = iter(iterable).generator();
var cache:Array = [];
var noCache:Boolean = true;
var i:uint = -1;
return function():* {
if (noCache) {
try {
var res:* = next();
cache.push(res);
return res;
} catch (e:StopIteration) {
noCache = false;
return arguments.callee();
}
} else {
if (cache.length == 0) stop();
i = (i + 1) % cache.length;
return cache[i];
}
};
});
}
/*
startから始まり、stepづつ増加または減少するstopまでの数列を返します
ただしstopは含みません。引数の与え方は以下
range(stop:Number)
range(start:Number, stop:Number, step:Number = 1)
*/
public static function range(...args):Iterable {
var start:Number = 0;
var stop:Number = 0;
var step:Number = 1;
if (args.length == 1) {
stop = args[0];
} else if (args.length == 2) {
start = args[0];
stop = args[1];
} else if (args.length == 3) {
start = args[0];
stop = args[1];
step = args[2];
} else {
throw new ArgumentError("range() takes 1, 2, or 3 arguments!");
}
if (step === 0) {
throw new ArgumentError("range() step must not be 0");
}
return new Iterable(function():Function {
return function():Number {
if ((step > 0 && start >= stop) || (step < 0 && start <= stop)) {
Iterable.stop();
}
var result:uint = start;
start += step;
return result;
};
});
}
/*
乱数列を返します
*/
public static function rand():Iterable {
return new Iterable(function():Function {
return function():Number {
return Math.random();
};
});
}
/*
eをn回繰り返した列を返します
n = -1で無限を意味します
repeat(e:*, n:int = -1)
*/
public static function repeat(e:*, n:int = -1):Iterable {
return new Iterable(function():Function {
return function():* {
if (n != -1 && n-- <= 0) stop();
return e;
};
});
}
private static function makeGenerator(it:*):Function {
if (it is Function)
return Function(it);
if ("generator" in it && it.generator is Function)
return it.generator;
var ary:Array = (it is Array) ? it as Array : values(it);
return function():Function {
var i:uint = 0;
var l:uint = ary.length;
return function():* {
if (i >= l) stop();
return ary[i++];
};
};
}
private static function values(obj:*):Array {
var ary:Array = [];
for each (var e:* in obj) ary.push(e);
return ary;
}
/*
反復から脱出します
*/
public static function stop():void {
throw new StopIteration();
}
private var generator:Function;
public function Iterable(generator:Function) {
this.generator = generator;
}
/*
配列化したものを返します
*/
public function toArray():Array {
var ary:Array = [];
each(function(e:*):void {
ary.push(e);
});
return ary;
}
/*
各要素を引数としてfを呼び出します
*/
public function each(f:Function):void {
var next:Function = generator();
while (true) {
try {
f(next());
} catch (e:StopIteration) {
break;
}
}
}
/*
各要素を引数としてfを呼び出した結果の列を返します
iterable0.map(iterable1, ... iterableN, f)
fの前に反復可能なオブジェクトを与えた場合、それらの要素も引数に加えてfを呼び出します。
f(elem0, elem1, ... elemN)
*/
public function map(...args):Iterable {
var f:Function = args.pop();
var iters:Array = [this].concat(args).map(function(e:*, ...rest):Function {
return iter(e).generator;
});
var l:uint = iters.length;
var nexts:Array = new Array(l);
return new Iterable(function():Function {
for (var i:uint = 0; i < l; ++i) nexts[i] = iters[i]();
var tuple:Array = new Array(l);
return function():* {
for (i = 0; i < l; ++i) tuple[i] = nexts[i]();
return f.apply(null, tuple);
};
});
}
/*
要素を組にした列を返します
iter([1, 2, 3]).zip(['one', 'two', 'three']).toArray()
は以下のようになります
[[1, 'one'], [2, 'two'], [3, 'three']]
*/
public function zip(...iters):Iterable {
return map.apply(null, iters.concat(function(...args):Array {
return args;
}));
}
/*
全ての要素が真なら真を返します。
引数に要素をテストする関数を与えた場合、全てのテストが真なら真を返します
*/
public function all(f:Function = null):Boolean {
var result:Boolean = true;
if (f != null) {
each(function(e:*):void {
if (!f(e)) {
result = false;
stop();
}
});
} else {
each(function(e:*):void {
if (!e) {
result = false;
stop();
}
});
}
return result;
}
/*
いずれかの要素が真なら真を返します。
引数に要素をテストする関数を与えた場合、いずれかのテストが真なら真を返します
*/
public function any(f:Function = null):Boolean {
var result:Boolean = false;
if (f != null) {
each(function(e:*):void {
if (f(e)) {
result = true;
stop();
}
});
} else {
each(function(e:*):void {
if (e) {
result = true;
stop();
}
});
}
return result;
}
/*
各要素をテストし、結果が真の要素からなる列を返します
*/
public function filter(f:Function):Iterable {
return new Iterable(function():Function {
var next:Function = generator();
return function():* {
while (true) {
var result:* = next();
if (f(result)) return result;
}
};
});
}
/*
startから始まりstopを含まない部分を返します
stepを指定すると間引きます
引数の与え方は以下
slice(stop:uint)
slice(start:uint, stop:uint, step:uint = 1)
*/
public function slice(...args):Iterable {
var start:uint = 0;
var stop:uint = 0;
var step:uint = 1;
if (args.length == 1) {
stop = args[0];
} else if (args.length == 2) {
start = args[0];
stop = args[1];
} else {
start = args[0];
stop = args[1];
step = args[2];
}
return new Iterable(function():Function {
var next:Function = generator();
var i:uint = 0;
return function():* {
while (true) {
var result:*;
while (i <= start) {
result = next();
i++;
}
if (start >= stop) Iterable.stop();
start += step;
return result;
}
};
});
}
/*
各要素と結果を元に、累積的に計算を行った各ステップでの結果の列を返します
memoは初期値です
*/
public function scan(memo:*, f:Function):Iterable {
return new Iterable(function():Function {
var next:Function = generator();
var result:* = memo;
return function():* {
result = f(result, next());
return result;
};
});
}
/*
各要素と結果を元に、累積的に計算を行い結果を返します
memoは初期値です
*/
public function fold(memo:*, f:Function):* {
var next:Function = generator();
var result:* = memo;
each(function(e:*):void {
result = f(result, e);
});
return result;
}
/*
valueを含むとき真を返します
*/
public function elem(value:*):Boolean {
var result:Boolean = false;
each(function(e:*):void {
if (e == value) {
result = true;
stop();
}
});
return result;
}
/*
テスト関数が真となる最初の要素を返します
*/
public function find(f:Function):* {
var result:* = null;
each(function(e:*):void {
if (f(e)) {
result = e;
stop();
}
});
return result;
}
/*
連結した列を返します
iter([0, 1]).chain([2, 3, 4], [5, 6]).toArray()
は以下のようになります
[0, 1, 2, 3, 4, 5, 6]
*/
public function chain(...args):Iterable {
if (args.length == 0) return this;
var iters:Array = [this].concat(args).map(function(e:*, ...rest):Function {
return iter(e).generator;
});
var l:uint = iters.length;
var nexts:Array = new Array(l);
return new Iterable(function():Function {
for (var i:uint = 0; i < l; ++i) nexts[i] = iters[i]();
return function():* {
try {
return nexts[0]();
} catch (e:StopIteration) {
nexts.shift();
if (nexts.length == 0) stop();
return arguments.callee();
}
};
});
}
/*
列を1重減らします
iter([['a', 'b'], 'hoge', ['c', 'd']]).concat().toArray()
は以下のようになります
['a', 'b', 'c', 'd']
*/
public function concat():Iterable {
return iter([]).chain.apply(null, toArray());
}
/*
先頭からテストし、テストの結果が偽になる要素の前までの列を返します
*/
public function takeWhile(f:Function):Iterable {
return new Iterable(function():Function {
var next:Function = generator();
return function():* {
var result:* = next();
if (!f(result)) stop();
return result;
};
});
}
/*
先頭からテストし、テストの結果が偽になる要素以降の列を返します
*/
public function dropWhile(f:Function):Iterable {
return new Iterable(function():Function {
var next:Function = generator();
try {
var result:* = next();
while (f(result)) {
result = next();
}
} catch (e:StopIteration) {
return function():void {
stop();
};
}
var head:Boolean = true;
return function():* {
if (head) {
head = false;
return result;
}
return next();
};
});
}
/*
要素のmethodをargsを引数として呼び出した結果の列を返します
*/
public function invoke(method:String, ...args):Iterable {
return map(function(e:*):* {
return e[method].apply(null, args);
});
}
/*
要素の持つpropertyからなる列を返します
*/
public function pluck(property:String):Iterable {
return map(function(e:*):* {
return e[property];
});
}
/*
正規表現にマッチする要素からなる列を返します
*/
public function grep(pattern:RegExp):Iterable {
return filter(pattern.test);
}
/*
重複要素を取り除いた列を返します
*/
public function uniq():Iterable {
var ary:Array = [];
return filter(function(e:*):Boolean {
if (ary.indexOf(e) == -1) {
ary.push(e);
return true;
} else {
return false;
}
});
}
/*
両方のいずれかに含まれる要素を全て含む列を返します
*/
public function union(it:*):Iterable {
return chain(it).uniq();
}
/*
集合の差演算
*/
public function diff(it:*):Iterable {
it = iter(it);
var ary:Array = [];
return filter(function(e:*):Boolean {
if (ary.indexOf(e) != -1 || it.elem(e)) {
return false;
} else {
ary.push(e);
return true;
}
});
}
/*
両方に含まれる要素からなる列を返します
*/
public function intersect(it:*):Iterable {
it = iter(it);
var ary:Array = [];
return filter(function(e:*):Boolean {
if (ary.indexOf(e) == -1 && it.elem(e)) {
ary.push(e);
return true;
} else {
return false;
}
});
}
/*
ランダムに選んだ要素を返します
*/
public function choice():* {
var ary:Array = toArray();
return ary[Math.floor(Math.random() * ary.length)];
}
/*
要素の順番をシャッフルしますランダムソート(笑)
*/
public function randomize():Iterable {
return iter(toArray().sort(function(...args):Number {
return (Math.random() < 0.5) ? -1 : 1;
}));
}
}
}
class StopIteration extends Error {
public function StopIteration() {
super('StopIteration');
}
}
enterFrameをトリガにしてゆっくりと反復するメソッドや、Deferredを要素とするリストをゆっくりと反復させるメソッドを実装すると面白いと思うのですが、それはまた余力があるときに。