[530] 名前のないクロージャで再帰呼び出し
投稿者：NykR
2007/02/20 02:13:25
はじめまして、「プログラミング言語を作る」楽しく読ませていただいています。
crowbarには再帰呼び出しのための名前付きのクロージャがありますが、名前のないクロージャでも、不動点演算子を使えば再帰呼び出しは可能です。
# 不動点演算子(2引数関数用)
function fp_op2(f) {
return closure(p) {
return p(p);
}(closure(x) {
return closure(g, h) { return f(x(x))(g, h); };
});
}
# 使用例。コードは(ぱ)さんの本にあったクイックソートをそのまま使わせていただきました
function quick_sort(data, less) {
fp_op2(closure(quick_sort_sub) {
return closure(left, right) {
pivot = data[(left + right) / 2];
left_index = left;
right_index = right;
while (left_index <= right_index) {
for (; less(data[left_index], pivot); left_index++) {}
for (; less(pivot, data[right_index]); right_index--) {}
if (left_index <= right_index) {
temp = data[left_index];
data[left_index] = data[right_index];
data[right_index] = temp;
left_index++;
right_index--;
}
}
if (left_index < right) {
quick_sort_sub(left_index, right);
}
if (left < right_index) {
quick_sort_sub(left, right_index);
}
};
})(0, data.size() - 1);
return data;
}
print("" + quick_sort({ 5,6,3,2,1,9,8,0,7,5,3,2,4,3 },
closure(lhs, rhs) { return lhs < rhs; }) + "\n");
# => (0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8, 9)
名前付きクロージャを使った方が簡単でわかりやすいですが(ついでに効率もいいです)、こういうのもありますよ、ということで投稿しました。
＃ 既にご存じでしたら申し訳ありません