2014年5月5日

再帰的なラムダ式

あまり実用的ではないが、.NET でラムダ式で再帰を行う方法はいくつかある。
ここでは、階乗を再帰の例とする。

ちなみに、普通の再帰メソッド。 

public static int Factorial(int x)
{
    return x > 1 ? x * Factorial(x - 1) : 1;
}

1. ラムダ式割り当て変数で再帰


Func<int, int> fac1 = null;
fac1 = x => x > 1 ? x * fac1(x-1) : 1;
ラムダ式内で、自身を割り当てる変数をメソッドとして使用する方法。
たぶん、一番シンプルな方法になる。
ただし、コンパイラの都合上、変数宣言と同時にラムダ式の代入はできない。
※「未割り当てのローカル変数 '～' が使用されました。」エラーが出る。

また、ひねくれた使い方をするとバグの原因になる。 

Func<int, int> fac1 = null;
fac1 = x => x > 1 ? x * fac1(x-1) : 1;
var fac1copy = fac1;
Console.WriteLine(fac1(4));     // 24
Console.WriteLine(fac1copy(4)); // 24

fac1 = x => x * x;
Console.WriteLine(fac1(4));     // 16 : 4 * 4
Console.WriteLine(fac1copy(4)); // 36 : 4 * fac1(3) = 4 * (3 * 3)

// fac1copy は最初の fac1 の内容から変わってないが、再帰として fac1 を使っているため、
// fac1 を変更すると影響を受けてしまう。

2. リフレクションで再帰


Func<int, int> fac2 = x =>
    x > 1 ? x * (int)MethodBase.GetCurrentMethod().Invoke(null, new object[]{x-1}) : 1;
リフレクションにより、自身を呼び出す方法。
javascript の arguments.callee （今や非推奨）に近い。
リフレクションなのでパフォーマンスはアレだが、1. のような副作用はない。

3. 不動点コンビネータで再帰

再帰メソッドを引数で渡せばいいかも？という発想から下記を定義する。 

Func<Func<int, int>, Func<int, int>> fac3base = (Func<int, int> f) => {
    return (int x) => {
        return x > 1 ? x * f(x - 1) : 1;
    };
};

// 型推論バージョン
// Func<Func<int, int>, Func<int, int>> fac3base = f => x => x > 1 ? x * f(x-1) : 1;

ここで、fac3base の引数は？ということに頭を悩ませると思う。
なぜなら、渡したい中身は fac3base に定義されているから・・・

とりあえず、Func<Func<int, int>, Func<int, int>> から Func<int, int> を取り出す処理、つまり、
Func<
  Func<Func<int, int>, Func<int, int>>,
  Func<int, int>
>
となるメソッド／ラムダが欲しい、ということで不動点コンビネータ（Fixed-point combinator）の出番である。

  • Z コンビネータ
wikipedia どおりの実装。 

// 自身を引数に持つデリゲート ※外部に定義する
delegate T SelfApplicable<T>(SelfApplicable<T> self);

Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> Z =
(Func<Func<int, int>, Func<int, int>> f) => {
    SelfApplicable<Func<int, int>> Z1 = (SelfApplicable<Func<int, int>> x) => {
        return f((int y) => {
            return x(x)(y);
        }
    };
    return Z1(Z1);
};

// 型推論バージョン
// Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> Z = f => {
//     SelfApplicable<Func<int, int>> Z1 = x => f(y => x(x)(y));
//     return Z1(Z1);
// };

// 使用方法
var fac3z = Z(fac3base);
Console.WriteLine(fac3z(4)); // 24

  • Y コンビネータ
ここの引用。
※C# による実装なので、厳密には Z コンビネータ 

// SelfApplicable は Z コンビネータと同じもの
SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>> Y =
(SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>> y) => {
    return (Func<Func<int, int>, Func<int, int>> f) => {
        return (int x) => {
            return f(y(y)(f))(x);
        };
    };
};
Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> YFix = Y(Y);

// 型推論バージョン
// SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>> Y =
// y => f => x => f(y(y)(f))(x);
// var YFix = Y(Y);

// 使用方法
var fac3y = YFix(fac3base);
Console.WriteLine(fac3y(4)); // 24

なんで動いてるの？という疑問については、wikipedia や引用元サイト参照。
不動点コンビネータとは、要するに fac3base に渡す引数を fac3base から作り出してくれるものである。

おまけ

3. の汎用メソッド 

public static class Combinators<TIn, TOut>
{
    static Combinators()
    {
        SelfApplicable<Func<Func<Func<TIn, TOut>, Func<TIn, TOut>>, Func<TIn, TOut>>>
        Y = y => f => x => f(y(y)(f))(x);
        YCombinator = Y(Y);
    }

    public static readonly
    Func<Func<Func<TIn, TOut>, Func<TIn, TOut>>, Func<TIn, TOut>> ZCombinator = f => {
        SelfApplicable<Func<TIn, TOut>> Z1 = x => f(y => x(x)(y));
        return Z1(Z1);
    };

    public static readonly
    Func<Func<Func<TIn, TOut>, Func<TIn, TOut>>, Func<TIn, TOut>> YCombinator;
}
public delegate T SelfApplicable<T>(SelfApplicable<T> self);

参考URL

投稿者 時刻:
ラベル: , ,

0 件のコメント:

コメントを投稿