今日はC#。

ツリービューにファイルツリーを表示するのを、
λ式で再帰的に書こうとしてみた。

 Action<string, TreeNodeCollection> func = null;
 func = (path, nodes) =>
 {
     TreeNode node = nodes.Add(Path.GetFileName(path));
     node.Tag = path;
     if (Directory.Exists(path))
     {
         Array.ForEach(
             Directory.GetDirectories(path).Concat(Directory.GetFiles(path)).ToArray(),
             child => func(child, node.Nodes));
     }
 };
 func(@"C:", treeView1.Nodes);

1行目、一度funcにnullを入れて、2行目でλ式を入れている。
こうしないと、func = の右辺ではまだfuncが未初期化なので再帰しようとしているところでコンパイルエラー。
ていうかかっこ悪い。


スマートにかけないのかと調べていると、Yコンビネータなるものにたどり着いてしまう。
よく分からないのだが、これを使うと再帰が綺麗にかけるらしい。

ぐぐった結果、こんな答えが出てきた。

 delegate Func<A, R> Recursive<A, R>( Recursive<A, R> f );

 Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> y = f =>
     ( (Recursive<int, int>)( g => a => f( g( g ) )( a ) ) )
     ( (Recursive<int, int>)( g => a => f( g( g ) )( a ) ) );

 var int120 = y( fact => n => n == 0 ? 1 : n * fact( n - 1 ) )( 5 );

5の階乗を再帰で求めている。
なるほど、確かにこれなら綺麗に書けるみたいだけど…
全く意味が分からない。

こんな感じのメソッド作っておけば…

 Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> func)
 {
     Func<Func<Func<A, R>, Func<A, R>>, Func<A, R>> y = f =>
         ((Recursive<Func<A, R>>)(g => a => f(g(g))(a)))
         ((Recursive<Func<A, R>>)(g => a => f(g(g))(a)));
     return y(func);
 }
 var func = Y<int, int>( fact => n => n == 0 ? 1 : n * fact( n - 1 ) );
 func(5); // 120

もうちょっと簡略化して、
 Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
 {
     Recursive<Func<A, R>> rec = g => a => f(g(g))(a);
     return rec(rec);
 }
うん。これなら実用できそう。
でもやっぱり理解不能。

というわけで、この記事を書いてみている。

■シンプルな関数で考えてみる。
0...3の和を計算する。
 Y<int, int>( func => arg => arg>0 ? arg + func(arg-1) : 0 )(3);
これを展開をしてみよう

 f = { func => arg => arg>0 ? arg + func(arg-1) : 0 }
 rec = g => a => f(g(g))(a);
 rec(rec)(3);

fを展開
 rec = { g => a => { arg => arg>0 ? arg + g(g)(arg-1) : 0 }(a) };
 rec(rec)(3);

recを展開
 { g => a => { arg => arg>0 ? arg + g(g)(arg-1) : 0 }(a) }({ g => a => { arg => arg>0 ? arg + g(g)(arg-1) : 0 }(a) })(3) --- (1.1)

さて、この形がこれから何度も出てくるので
 func = { g => a => { arg => arg>0 ? arg + g(g)(arg-1) : 0 }(a) }({ g => a => { arg => arg>0 ? arg + g(g)(arg-1) : 0 }(a) });
と置こう。最初のfuncとは違うけど、同じです。
funcは展開すると
 { a => { arg => arg>0 ? arg + func(arg-1) : 0 }(a) } --- (1.2)
となる。
見ての通り再帰になっている。

funcを用いると式(1.1)は
 func(3)

式(1.2)より
 { a => { arg => arg>0 ? arg + func(arg-1) : 0 }(a) }(3)

aを3に展開
 { arg => arg>0 ? arg + func(arg-1) : 0 }(3)

argを3に展開
 3>0 ? 3 + func(3-1) : 0

3項演算子の結果が確定するので取り出す。
 3 + func(2)

もう一度funcを展開すると…
 3 + { a => { arg => arg>0 ? arg + func(arg-1) : 0 }(a) }(2)

後半部分がさっき出てきた形になっているので、以下同様に
 3 + { arg => arg>0 ? arg + func(arg-1) : 0 }(2)
 3 + 2 + { arg => arg>0 ? arg + func(arg-1) : 0 }(1)
 3 + 2 + 1 + { arg => arg>0 ? arg + func(arg-1) : 0 }(0)
argが0に展開され、0>0==falseとなるので
 3 + 2 + 1 + 0
めでたしめでたし。


■この証明を一般化してみよう。

Yに渡すfは一般に次のような形になる。
 f = func => arg => F(func, arg)
（上記の例ならF = (func, arg) => arg>0 ? arg + func(arg-1) : 0 ）

Y(f)(arg)を展開していこう。
fを展開
 Y({ func => arg => F(func, arg) })(arg);

Yを展開
 rec = g => a => { func => arg => F(func, arg) }(g(g))(a);
 rec(rec)(arg);

funcを展開
 rec = g => a => { arg => F(g(g), arg) }(a)
 rec(rec)(arg);

argを展開
 rec = g => a => F(g(g), a);
 rec(rec)(arg);

recを展開
 { g => a => F(g(g), a) }({ g => a => F(g(g), a) })(arg); --- (2.1)

gを展開
 { a => F({ g => a => F(g(g), a) }({ g => a => F(g(g), a) }), a) }(arg);

aを展開
 F({ g => a => F(g(g), a) }({ g => a => F(g(g), a) }), arg); --- (2.2)

ここで、
 func = { g => a => F(g(g), a) }({ g => a => F(g(g), a) });
とおくと、
式(2.1)は次のようになる。
 func(arg);

式(2.2)は次のようになる。
 { a => F(func, a) }(arg);

argを展開
 F(func, arg);

Fでは、次のような呼び出しを行うだろう。
 func(arg_1)

するとこれは、次のように展開される。
 F(func, arg_1);

そして再帰的にFが呼ばれることになる。
 F(func, arg_n);

再帰の終了となるarg_Nが渡された時点で、Fの呼び出しが終了し、展開も終了する。

このfuncがY<A, R>()の返す式の正体だ。

ということで良いのかな。


参考：
C#λ式で再帰をやろうとしてYコンビネータに行き着くパターン（今回の自分と同じ）
http://blogs.wankuma.com/mnow/archive/2008/02/17/123545.aspx
http://blogs.msdn.com/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx

Yコンビネータそのものの解説
http://d.hatena.ne.jp/nowokay/20090409