K.Maebashi's BBS 投稿フォーム

ハンドル名
件名
Link

>はじめまして、「プログラミング言語を作る」楽しく読ませていただいています。
>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)
>
>名前付きクロージャを使った方が簡単でわかりやすいですが(ついでに効率もいいです)、こういうのもありますよ、ということで投稿しました。
>＃ 既にご存じでしたら申し訳ありません

spamよけのため、ここに「ほげぴよ」と入力してください。

削除パスワード : クリック！