問題タブ [y-combinator]

注: これは一種の宿題であり、そうではありません。最終的な目標は、数値のリストとして関数に提供される一連の数値の累乗を生成する関数を作成することです。関数の再帰バージョンがありますが、ソリューション内の明示的な再帰関数 ( など) を同等のラムダのみの式に置き換えるいくつかの方法を見つける必要がありappendますmapm。

そのため、小さな問題から始めて、それらをすべて組み合わせて完全な関数を作成したいと考えています。純粋なラムダ (Y コンビネーター) を使用して非再帰的な階乗関数を思い付くことができましたが、現在、リスト内のすべての数値を 2 乗する素敵な関数を考え出そうとしています。ジャンプする前に小さな問題を解決しようとしています。乗算再帰関数まで:

上記のコードは、その前に Y コンビネータが存在するにもかかわらず、再帰しません。適切なパラメータを内部の関数に渡す際に問題が発生していることは明らかです。アイデアはありますか?

私は最大部分列和問題を解決しようとしていて、ネイトの解決策を思いつきました

ラッパー関数msssを呼び出すと、次に が呼び出さfれ、実際に処理が実行されます。解決策は良好で、正しく機能しています。なんらかの理由で、製品コードで最大部分列和問題を解かなければならない場合、それが私のやり方です。

しかし、そのラッパー関数は本当に私を悩ませます。Haskell では、プログラム全体を 1 行で書くことができるほど粘り強く、プログラムがほとんど 1 つの大きな式に過ぎないという点を真に強調する方法が気に入っています。そこで、余分な課題のためにラッパー関数を排除しようと考えました。

今、私は古典的な問題に遭遇しました: 匿名の再帰を行うには? 関数に名前を付けることができない場合、どのように再帰を行いますか? ありがたいことに、コンピューティングの父たちはずっと前に固定小数点コンビネーターを発見することでこの問題を解決しました。最も人気のあるものはY コンビネーターです。

Yコンビネーターをセットアップするためにさまざまな試みをしましたが、コンパイラーを通過できません。

ただ与える

から に変更 f (y y f)するf (y f)だけで

コンビネータを外部で定義するだけで別のアプローチを試みましたが、これはまだ機能せず、1 つの式でそれを行うという私の課題を実際には満たしていません。

私がしていることのどこが悪いのか分かりますか? 私は途方に暮れています。Haskell はそういうものばかりだと思っていたからです。無限のデータ構造を持っているのに、なぜ無限型に問題があるのでしょうか? 型付けされていないラムダ計算が矛盾していることを示したパラドックスと関係があると思います。よくわかりませんが。誰かが明確にできれば良いでしょう。

また、再帰は常にfold関数で表現できるという印象を受けました。折り目を使用するだけでそれを行う方法を誰かに教えてもらえますか? ただし、コードが単一の式であるという要件は依然として有効です。

約 8 億回呼び出す必要がある再帰関数 (C#) があります。これは明らかに通常、約 900 回目の呼び出しの後にスタック オーバーフローを引き起こします。私はこれを複数のループに追い出しましたが、再帰パターンは非常に簡単で、維持するのがきれいです。

私が読んで見たものから、スタックオーバーフローの問題を解決し、複数のネストされたループを修正する必要があるように、yコンビネーターを使用して再帰関数を実装することを検討しています。

y-combinator を使用した経験のある人はいますか? スタック オーバーフローでスタックすることはありますか?

階乗の簡単な例を見てみましょう。5,000 などより大きいほとんどの数値の階乗は、スタック オーバーフローを引き起こします。そのシナリオで y-combinator を適切に使用した場合、スタック オーバーフローは修正されますか?

実装するのは簡単ではないように見えるので、開発努力/リソースを y-combinator の実装と学習に費やす前に確認したいと思います。

なぜこの関数の型は (a -> a) -> a なのですか?

無限/再帰型であるべきではありませんか? 私はそれがタイプであるべきだと思うものを言葉にしようとしましたが、何らかの理由でそれを行うことができません.

f (yf) がどのように値に解決されるのかわかりません。以下は私にとってもう少し理にかなっています：

しかし、それはまだばかげて混乱しています。どうしたの？

y-combinatorを使用してscalaでgcdを定義しようとしています：

しかし、エラーが発生します：

私がすべての議論をカレーすれば、問題はありません：

カレーなしのバージョンで何が間違っていますか？

Y-Combinatorを1時間理解しようとした後、ようやく理解できましたが、ほとんどの場合、それがなくても同じことが達成できることに気付きました...その目的を完全に理解しているかどうかはわかりませんが。

例えば。Y-Combinatorを使用した階乗

別のラムダの関数への参照を持つことによる階乗

PythonでY-Combinatorの目的があるかどうか誰か教えてもらえますか？

私はこの割り当てを行う必要があります。そこでは、間違って書かれた再帰的プロシージャを解析し、それを修正する必要があります。例：これ：

これに変換します：

手順は、「let」、letの、およびbodyの3つの部分からなる引用として示されています。2番目の部分を解析したい（つまり、その中のすべての用語が「let」の表現から1つの単語になるリストを作成したい）が、何を試してもうまくいかないようです。

私はdrRacketスキームを使用しています。

長いメッセージをありがとう、ごめんなさい。

そのため、この関数用に適用可能なYコンビネータが開発されているTheLittleSchemerの第9章の終わりを読んで再読することに多くの時間を費やしましたlength。私の混乱は、2つのバージョンの長さ（コンビネータが除外される前）を対比する単一のステートメントに要約されると思います。

170ページ（第4版）は、A

引数に適用すると関数を返します

Bが

関数を返しません

これにより、自己アプリケーションの無限後退が発生します。私はこれに困惑しています。Bがこの問題に悩まされている場合、Aがどのようにそれを回避するのかわかりません。

Y コンビネータに関するウィキペディアの記事では、Y コンビネータの次の JavaScript 実装が提供されています。

JavaScript に Y コンビネータが存在することは、すべての JavaScript 関数が不動点を持つことを意味するはずです ( for every function g, Y(g)andg(Y(g))は等しい必要があるため)。

ただし、違反する不動点のない関数を考え出すことは難しくありませんY(g) = g(Y(g))(こちらを参照)。特定の汎関数でさえ不動点を持たない (こちらを参照)。

すべての関数が不動点を持つという証明は、与えられた反例とどのように調和しますか? Y(g) = g(Y(g))JavaScript は、証明が適用される型指定されていないラムダ計算ではありませんか?

これがコードです（これもここにあります）：

私がそれを実行するとき：

スクリーンショットは次のようになります。

担当者としてDrRacketを使用しています。コードの何が問題になっていますか？