Hatena::Groupocaml-nagoya

yoshihiro503の関数的日記

2008-11-27 (Thu)

haXeで不動点演算子(fixed point operator)

| 18:27 | haXeで不動点演算子(fixed point operator) - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - haXeで不動点演算子(fixed point operator) - yoshihiro503の関数的日記

haXeでは関数が第一級なので、次のように関数内での変数宣言でローカル関数を定義することが出来る。

function hoge (a, b) {
  var f = function (x) { return 2*x + 1; };
  return f (a) + f (b);
}

このため、補助関数を隠蔽したりできてとても便利である。しかし、次のような場合に、fact_iter補助関数をfact関数内で定義しようと思うと、ちょっと問題が生じる。

function fact (n) {
  return fact_iter (1, n);
}
function fact_iter (a, n) {
  if (n == 0) return a;
  else return fact_iter(n*a, n-1);
}

fact_iter関数は自分自身を呼ぶ再帰関数だからだ。

function fact (n) {
  var fact_iter = function (a, n) { 
    if (n == 0) return a;
    else return fact_iter(n*a, n-1);
  }
  return fact_iter (1, n);
}

とはできない。

再帰する補助関数を関数内で宣言したくて次のような項を定義した。

function fix<A, B> (f : (A -> B) -> A -> B) {
  return function (x) {
    return f (fix (f), x);
  }
}

このfixという項を使えば、先ほどの再帰する補助関数を内部に隠蔽することが出来る。

function fact (n) {
  var local = fix (function (f, s_n) {
    return switch (s_n) {
	case pair(store, n):
	  if(n == 0)  store;
          else f (n*store, n-1);
	}
  });
  return local (pair(1, n));
}

ValnirValnir2012/04/08 18:01Thanks guys, I just about lost it lokonig for this.