Hatena::Groupocaml-nagoya

yoshihiro503の関数的日記

2010-06-09 (Wed)

haXeで怠惰(lazy)を実装してみた

| 23:31 | haXeで怠惰(lazy)を実装してみた - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - haXeで怠惰(lazy)を実装してみた - yoshihiro503の関数的日記

haXeには組み込みでは怠惰(lazy)評価 機能が備わっていないようだったので実装してみた。

関数型言語ではthunkを簡単に扱うことができ、評価を遅延させることができるが、それだとタダの遅延評価(delay evaluation)になってしまい、無駄な計算が発生してしまうかもしれない。そこで評価は遅らせるけれど、一回計算したら覚えておくというLazy型を定義した。コンストラクタにはthunkをわたして使う。

enum Option<X> {
    None;
    Some(x : X);
}

class Lazy<A> {
    var _x : Option<A>;
    var _getter : Void -> A;

    public function new (getter) {
        this._x = None;
        this._getter = getter;
    }

    public function force() {
        switch (this._x) {
            case None:
                var x = this._getter();
		this._x = Some(x);
		return x;
	    case Some(x):
		return x;
	}
    }
}

そして、それを使って怠惰リストを実装したのが次。

enum LListT<A> {
    LNil;
    LCons(x : A, tl : Lazy<LListT<A>>);
}

class LList{
    static public function from(n : Int) : LListT<Int> {
	return LCons(n, new Lazy(function() return from(n+1)));
    }

    public static function take<A>(n:Int,xs:LListT<A>) : List<A> {
	var ys = new List();
	var xs0 = xs;
	for (i in 0...n) {
	    switch (xs0) {
		case LCons(x, xs1):
		    xs0 = xs1.force();
		    ys.push(x);
		case LNil:
		    break;
	    }
	}
	return Util.list_reverse(ys);
    }

    public static function filter<A> (xs : LListT<A>, f:A -> Bool) {
	return switch(xs) {
	    case LNil: LNil;
	    case LCons(x, xs):
		if (f(x)) LCons(x, new Lazy(function ()
		   return filter(xs.force(), f)));
		else filter(xs.force(), f);
	}
    }
}

以上の怠惰評価と怠惰リストをUtil.hxというファイルにまとめて、これを試してみるために素数の無限列を作ってみた。

import Util;

class Test {
    static function main() {
	trace("primes: "+LList.take(100,primes));
    }

    static var primes = seive(LList.from(2));
		
    static function seive(xs) {
	return switch(xs) {
	    case LNil: Util.failwith("");
	    case LCons(x,xs): LCons(x, Util.lazy(function() {
		return LList.filter(seive(xs.force()), function(a) return a%x!=0);
	    }));
	}
    }
}

TestクラスはTest.hxに保存。実行結果は以下。

 $ haxe -main Test -neko Test.n
 $ neko Test.n
Test.hx:7: primes: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 
193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 
311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 
433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541}