[2012-02-06 23:20 誤字訂正]
暇潰しネタ。

関数型言語の世界では、計算機論の基礎のひとつ、不動点コンビネータの実装が頭の体操のための題材になることが多い。
一方、手続型言語ではどうかというと、この関数の実装を行うには、関数を動的に生成して返さなければならないため、古い言語では実装することができなかった。(アーキテクチャ固有のハックをすれば別だけど)
しかし、ラムダ式だのデリゲートだのが使える最近の言語なら手続型でも実装できるはず。
手続型言語で不動点コンビネータを実装すれば、慣れている分、分かりやすかったりしないかな？ と思い、D言語で書いてみた。多引数対応。

R delegate(TS) fix(R, TS...)(R delegate(R delegate(TS), TS) f)
{
    class Wrapper(F)
    {
        public F delegate(Wrapper!(F)) func;
        public this(F delegate(Wrapper!(F)) func)
        {
            this.func = func;
        }
    }
 
    return delegate R delegate(TS)(Wrapper!(R delegate(TS)) g)
    {
        return delegate R(TS xs)
        {
            return f(g.func(g), xs);
        };
    }(new Wrapper!(R delegate(TS))(delegate R delegate(TS)(Wrapper!(R delegate(TS)) g)
    {
        return delegate R(TS xs)
        {
            return f(g.func(g), xs);
        };
    }));
}

うん。分かりづらい。これならむしろ関数型言語で素直に書いた方が分かりやすいかもorz

せっかくなので使い方の例をいくつか。

    // 階乗計算
    auto fact = fix(delegate int(int delegate(int) f, int n)
    {
        if(n <= 0)
        {
            return 1;
        }
        else
        {
            return n * f(n - 1);
        }
    });
    writefln("%s", fact(7)); // 5040

    // int配列からdouble配列への写像
    auto map = fix(delegate double[](double[] delegate(double delegate(int), int[]) f, double delegate(int) trans, int[] a)
    {
        if(a.length == 0)
        {
            return [];
        }
        else
        {
            return trans(a[0]) ~ f(trans, a[1 .. $]);
        }
    });
    // 配列の各要素を3で割ったものを得る
    writefln("[%s]", map(delegate double(int x){ return x / 3.0; }, [1, 3, 5, 7, 9, 11])); // [0.333333 1 1.66667 2.33333 3 3.66667]

    // たらい回し関数 （竹内関数)
    auto tak = fix(delegate int(int delegate(int, int, int) f, int x, int y, int z)
    {
        if(x <= y)
        {
            return y;
        }
        else
        {
            return f(f(x - 1, y, z), f(y - 1, z, x), f(z - 1, x, y));
        }
    });
    writefln("%s", tak(10, 5, 0)); // 10

# 実用性？ 知らん。