問題タブ [y-combinator]

固定小数点コンビネータが何であり、何に使用されるかを学ぶために、私は自分自身を書きました。しかし、ウィキペディアの例のように、厳密に匿名の関数で記述する代わりに、define を使用しました。

階乗とフィボナッチの汎関数でこれをテストしましたが、うまくいくようです。これは、固定小数点コンビネータの正式な定義を満たしていますか?

私は最近、Y コンビネータについて頭を悩ませていましたが、通常は次のように (多かれ少なかれ) 定義されていることがわかりました (これは C# ですが、言語の選択は重要ではありません)。

それは完全に機能しますが (しゃれが意図されています)、私の定義ははるかに単純であるように思われます。

後者の定義が一般的ではない理由はありますか (私はまだネット上で見つけていません)。それは、Y 自体を定義することと何か関係があるのでしょうか?

相互再帰関数のタプルを作成するための固定小数点コンビネータはありますか？つまり、Y-Combinatorのようなものを探していますが、複数の「再帰的」*関数を取り、関数のタプルを返しますか？

*：もちろん、通常のY-Combinatorの方法で、自分自身（および兄弟）を引数として取るように記述されているため、実際には再帰的ではありません。

数日前、「C# での匿名再帰」についてこのサイトにアクセスしました。この記事の主旨は、次のコードは C# では機能しないということです。

次に、カリー化とY コンビネーターを使用して C# の「匿名再帰」に戻る方法について詳しく説明します。これは非常に興味深いですが、私の日常のコーディングには少し複雑です。この時点で少なくとも...

私は自分の目で見るのが好きなので、Mono CSharp REPLを開いてその行に入りました。エラーなし。ということで、入りfib(8);ました。驚いたことに、うまくいきました！REPL は21!で応答しました。

これは REPL の魔法かもしれないと思ったので、「vi」を起動し、次のプログラムを入力してコンパイルしました。

それも完璧に構築され、実行されました！

Mac で Mono 2.10 を実行しています。現在、Windows マシンにアクセスできないため、Windows 上の .NET でこれをテストすることはできません。

これは .NET でも修正されていますか、それとも Mono のサイレント機能ですか? 記事は数年前のものです。

Mono のみの場合、次の就職の面接が待ちきれません。そこでは、.NET が機能しないという警告を提供する必要がある言語 (Mono C#) でフィビノッチ関数を作成するように求められます。まあ、実際、私は仕事が好きなので待つことができます。それにしても面白い…

アップデート：

fib名前付きデリゲートとして使用しているため、Monoは実際には「匿名」再帰を行っていません。私の悪い。nullMono C# コンパイラが代入前の値を想定するという事実は、fib以下に示すバグです。私が「コンパイラ」と言ったのは、.NET C# コンパイラがコードをコンパイルしなくても、.NET CLR は結果のアセンブリを問題なく実行できるからです。

そこにあるすべてのナチスのインタビューについて：

反復バージョンに置き換えることができます:

C# のような言語では再帰バージョンが非効率的であるため、これを実行する必要がある場合があります。メモ化の使用を提案する人もいるかもしれませんが、これは反復的な方法よりもまだ遅いため、単に気まぐれである可能性があります。:-)

ただし、この時点で、これは他の何よりも関数型プログラミングの宣伝になります (再帰バージョンの方がはるかに優れているため)。元の質問とはまったく関係ありませんが、回答の一部は重要だと考えていました。

だから私は y-combinator と匿名関数をいじっていて、この奇妙なエラーに遭遇しました:

（エラーを作成するソースコードと、最終的に動作するようになったバージョン）

ランク N ポリモーフィズム (use )を避けるために型を少し変更するforall b. Int -> b -> [b] -> [b]と、エラーは次のようになります。

forall b. b -> [b] -> [b]なぜ議論がないのか誰かが私に説明でき ますか?

反復の観点から不動点を計算する関数があります。

これから次のように抽象化できることに注意してください。

この関数は修正の観点から書くことができますか？このスキームから修正されたものへの変換があるはずのようですが、私にはわかりません。

私はYコンビネーターをよりよく学び(Schemeである程度理解している)、D 2.0で実装しようとしていますが、かなり惨めに失敗しています:

渡せないという明白な理由により、これは機能しませんfact(factその型は何でしょうか?)。その上、 の名前を自分自身に渡す必要があるfactので、いずれにしても機能しませんよね?

しかし...どうすればDでYコンビネーターを実装できますか?

私は JavaScript でコンビネータをいじっていて、S を動作させることを (できれば) 誇りに思っていましたが、ウィキペディアに出くわしたとき、「Y コンビネータは、SKI 計算で Y = S (K (SII)) ( S (S (KS) K) (K (SII)))」なので、それを試してみる必要がありました。

私は何を間違っていますか？私はその表現を正しく翻訳していませんか? これについて私が行っている方法に何か問題がありますか？それは理にかなっていますか？このようなものについて読まなければならないことのほとんどは、私の脳を爆発させたくなるだけなので、この演習の主なポイントは、表記法を理解しているかどうか (したがって、JavaScript に変換できるかどうか) を確認することでした。

ああ、ところで、私が再び読んだりいじったりしたのは、prototype.js が Prototype.K として実装しているものは、実際には I コンビネータであるということでした。誰か気づいた？

私の脳は自虐モードにあるようで、これ、これ、およびこれに溺れた後、C＃でDIYをいじりたいと思っていました。

私はYコンビネーターではないと思いますが、それ自体を参照せずに、非再帰関数を再帰的にすることができたようです:

したがって、これらを考えると：

これらを生成できます。

Kコンビネータはで、K := (λxy.x)固定小数点コンビネータはY := λf.(λx.f x x) (λx.f x x)です。私は計算しようとしましたYK：

YKは の不動点だからですK:

任意の e。しかし、KIeに等しい必要がありますI!