問題タブ [fixpoint-combinators]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票する
2 に答える
122 参照

haskell - Haskell の "fix" キーワードが再帰ラムダ関数の宣言に失敗しました

関数には再帰的な名前を付ける必要があるようです (それ自体を呼び出すため)。では、ラムダ関数はどのように再帰的になりますか?

ウィキペディアを検索したところ、これは「Yコンビネーター」で実行できると書かれています。私は数学理論のバックグループをあまり持っていません.「Yコンビネータ」がHaskell自身によって発見されたことを教えてくれます. Haskell 言語で "fix" キーワードと呼ばれる、私が試した:

失敗したようですが、「修正」キーワードを使用して期待したことを行うにはどうすればよいですか?

0 投票する
1 に答える
110 参照

haskell - Haskell の型と再帰の修正の例

コードに再帰ラムダを含めることに興味があったため、修正について読んでいるときに、この特定のコード例に出くわしました(Hereから):

fix の型シグネチャを無視すると、そのコードに何か問題があるように感じます。

修正(a -> a) -> aのタイプはラムダのタイプですが、(a -> a) -> a -> aこのコードを間違って読んでいると確信していますが、最初に読んだ方法は「修正は2つの引数に適用されます」でした。修正は1つの引数しか受け入れないため、これは間違っています、関数 (a -> a)、明らかに欠けているものがあるに違いありません。

a -> a -> a次に、ラムダのタイプと修正のタイプを調べたところ、「ちょっと待ってください。大きな不一致はありませんか? カリー化された関数を使用すると、引数が不十分なタイプの関数をフィードできることがわかります。新しい関数を作成しますが、ここでは関数にフィード(a -> a) -> a -> a(a -> a) -> aています。間違った引数を修正関数にフィードして、象をピンホールに通そうとしているようです。

内部パーサーと型チェッカー (brain 1.0) がこの行を評価する際にどこで問題が発生したのでしょうか?

0 投票する
4 に答える
913 参照

functional-programming - 継続渡しスタイルで固定小数点コンビネータを定義する

  • 固定小数点コンビネータは、再帰を導入するための非常に便利なツールです。
  • Continuation-Passing スタイルは、関数が決して返らないラムダ計算のスタイルです。代わりに、プログラムの残りの部分をラムダ引数として関数に渡し、それらを続行します。これにより、実行フローをより適切に制御し、さまざまなフロー変更構造 (ループ、コルーチンなど) をより簡単に定義できます。

しかし、ひとつひとつを表現できるかどうかは疑問です。私が見たすべての CPS スタイルの言語には、FIX再帰を定義するための明示的な構造があります。

  • なしでは、プレーンな CPS で固定小数点コンビネータ (または類似のもの) を定義できないためFIXですか? もしそうなら、あなたはそのようなことの証拠を知っていますか?
  • それともタイピングの問題だけですか?
  • それとも可能かもしれませんが、何らかの理由で非現実的ですか?
  • それとも、そこにある解決策が見つからなかっただけですか...?

Y コンビネータのような CPS 関数が次のように機能することを期待しCPSYます。Y 対応の CPS 関数を定義すると、次のようになります。

次に、それを入れて、CPSYそれ自体に再帰する関数を生成します。

CPSY、再帰に依存しない単純な継続渡しスタイルの関数である必要があります。Y コンビネータは、組み込みの再帰を使用せずに、単純なラムダ計算でこのような方法で定義できます。なんらかの形で CPS にも存在できますか?


明確にするために繰り返します:私はコンビネータのような関数CPSYを探しています:

  • CPS 関数の再帰を有効にします
  • it の定義は再帰に依存しません
  • it の定義は、継続渡しスタイルで与えられます (の本体内のどこにもラムダを返しませんCPSY) 。
0 投票する
1 に答える
95 参照

haskell - 固定小数点コンビネータのタイプの推測

私の質問は「固定小数点コンビネータ」に関連しています。このウィキペディアのページセクションによるとfix

タイプです(または少なくともタイプにすることができます)

誰かが私に理由を説明できますか?

0 投票する
3 に答える
1363 参照

haskell - このバージョンの「修正」が Haskell でより効率的なのはなぜですか?

Haskell では、これは不動点の単純な (単純な) 定義です。

しかし、Haskellが実際にそれを実装する方法は次のとおりです(より効率的です)

私の質問は、なぜ 2 番目のものは最初のものよりも効率的ですか?

0 投票する
1 に答える
439 参照

haskell - Y-コンビネータの使い方; この無限再帰が 9 を返すのはなぜですか?

Y - コンビネータ

私はY-コンビネーターについて学ぼうとしており(その説明も素敵です) 、このwikiの例に出くわしました。この件に関する詳細な説明は、Haskell または Python のいずれかで大歓迎です。お願いします!

コード

問題

が適用されたときに呼び出された関数がfix返されますが、その理由はわかりません。スタックをたどると、 が視覚化されます。9fix(\x -> 9)f(f ... (fix f) ...)

0 投票する
1 に答える
272 参照

haskell - 関数の最小固定点を見つける

この Haskell 関数がある場合:

次の Haskell 関数fを考えてみましょう:

では、固定点最小固定点(閉じた形式)を計算するにはどうすればよいでしょうか?

この質問に対する答えは次のとおりです。

ここに画像の説明を入力

この最小固定点はどのように計算されますか? 私はこれを理解しようとしていますが、まだ運がありません。誰かが私にこれを説明できれば素晴らしいことです。