これはstatic Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> F) { return t => F(Fix(F))(t); }
で、こうなりました。
static public IEnumerable<int> Fib(int count) { foreach (int ii in Enumerable.Range(0, count)) yield return Fix((Func<Func<int, int>, Func<int, int>>) (ff => i => ((i < 2) ? 1 : ff(i - 1) + ff(i - 2))))(ii); }これすっっげぇ・・（゜゜
で、でも使い方あってんのかわかんない；
Y Combinatorが凄すぎる！ - yuji1982の日記(改行を足しました)
yield return Fix<int>(ラムダ式)(ii);ってやるとキャストが要らない。型推論だけの重箱の隅つっこみ。
ところで、上のFix関数の定義だと、定義内でFixを再帰呼び出ししているので、厳密にはラムダ計算で言うところのYコンビネータではないと思う（ただし、同じ働きをする）。どう書く?.orgに同様の議論有り。
C#で真のYコンビネータを書けるのだろうか。ちょっと無理っぽい。g(g)と書けるFunc<>って存在するのか？存在しないよなあ……と、上の議論を見直してみたらちゃんと書いてあった。nobsun++
dankogaiもHaskellをネタにして同じこと書いてる。
(追記)NyaRuRuさんの「熟練した C# 使いは再帰を書かない？」と、そこからリンクされている過去記事は必読。そう、末尾再帰の最適化をやらない言語には、それ相応の書き方があるのだ。
(追記2)コメント欄が盛り上がりました。まずdelegateを使えばよいという例が示され、次にそのdelegateを再帰定義にすれば型問題も解決するという例が示された。勉強になりましたー。
>yield return Fix<int>(ラムダ式)(ii);
返信削除あーーなるほど!!気づきませんでした＞＜
ありがとうございます!
yield return Fix(((Func<int,int> ff) => ...
なら大丈夫なのかーぐらいしか気づいてませんでした。
厳密なYコンビネータの話は難しいですね・・^^;
C#で真のY Combinatorはキャスト駆使すれば見た目はすごく
返信削除醜いですが、できます。C# 3.0の処理系が手元に無いので
C# 2.0ですが、以下のようになります。
using System;
delegate object fn(object arg);
class YCombinatorTest
{
static void Main(string[] args)
{
fn y = delegate(object f) {
return ((fn)delegate(object proc) {
return ((fn)f)(
(fn)delegate(object arg) {
return ((fn)((fn)proc)(proc))(arg);
}
);
})((fn)delegate(object proc) {
return ((fn)f)(
(fn)delegate(object arg) {
return ((fn)((fn)proc)(proc))(arg);
}
);
});
};
fn fact = delegate(object f) {
return (fn)delegate(object n) {
if(((int)n) == 0) {
return 1;
} else {
return ((int)n) * ((int)((fn)f)(((int)n) - 1));
}
};
};
Console.WriteLine("fact(6) == {0}", ((fn)y(fact))(6));
}
}
あと、手前味噌ですが、以前JavaでY Combinatorを書いたので、
よろしければご覧ください。
http://www.coins.tsukuba.ac.jp/~i021216/diary/?date=20051101
> yuji1982さん
返信削除抽象度が高いものをまるっと理解するのは手ごわいですよね。
> みずしまさん
object型かあ。確かにdelegateもobjectだし、パラメータと戻り値の型をobjectにすれば、静的に型が決まらなくても問題ないわけですね。
Java版のほうですが、コンビネータなら匿名内部クラスで問題なく書けますね。(外部クラスのfinalフィールドしか触れなくても関係ない)
みずしまさんのアイデア、おもしろいですね！せっかくなのでラムダ式にしてみました。
返信削除// Y = λf.(λx.f(x x)) (λx.f(x x))
fn y = f =>
( ( fn ) ( proc => ( ( fn ) f )( ( fn ) ( arg => ( ( fn ) ( ( fn ) proc )( proc ) )( arg ) ) ) ) )
( ( fn ) ( proc => ( ( fn ) f )( ( fn ) ( arg => ( ( fn ) ( ( fn ) proc )( proc ) )( arg ) ) ) ) );
fn fact = f => ( fn ) ( n => ( int ) n == 0 ? 1 : ( int ) n * ( int ) ( ( fn ) f )( ( int ) n - 1 ) );
このYはCurryの不動点演算子と呼ぶそうです。
> siokoshouさん
返信削除ありがとうございます。キャストは消せないとはいえ、やっぱりラムダ式の方が見やすくなりますね。
http://blogs.msdn.com/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx
返信削除こちらの記事にほとんど書いてありますけどデリゲートを用意すればタイプセーフにできますね。
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 );
> taguoさん
返信削除わ、delegateを再帰定義にすればいいのか。
ありがとうございました！すっきりしました！
Wesのブログのことは知らなかったのですが、LINQや関数型言語の話が満載なんですね。モナドとか継続渡しとかの話も書いてあるし。
返信削除まとめて読んでみます。