問題タブ [fixpoint-combinators]

このコード例を見てください (現時点では非常に非効率的であることは無視してください)。

これは、F# で頻繁に発生する一般的なパターンです。ある値に対して自分自身を再帰する内部関数が必要です。この関数は 1 回だけ必要です。何らかの方法で、その内部からラムダを呼び出すことは可能ですか?魔法のキーワードか何か）？コードを次のようにしたいと思います。

しかし、ご想像のとおり、無名関数自体を参照する方法はありません。これは、##RECURSE## を配置する場所で必要になります。

私はコンビネータについて学ぼうとしていますが、( Y overriding self-application ) で与えられた例を理解するのに苦労しています。概念を理解し始めていると思いますが、まだ理解には程遠いです。

次のコードを Python に翻訳したいと思います。

私は次のように書いて「文字通りの」翻訳を試みました：

しかし、これは機能しません (関数がラムダ内で評価される順序に関係していると思います)。

だから私は関数合成を次のように使用しようとしました:

コードの最後のスニペットを呼び出すと、ラムダが返されます。

それで、Pythonで与えられた例の「リテラル」翻訳を書くことは可能ですか? どうすればできますか？

固定小数点コンビネータの使用例のほとんどは、整数を整数にする関数 (階乗など) を含みます。多くの場合、実数上の関数の不動点は、任意の有理数またはおそらく無理数になります (有名な例は、ロジスティック マップhttp://en.wikipedia.org/wiki/Logistic_mapです)。）。このような場合、不動点はプリミティブ型で表現されないことがあります (ただし、Clojure は比率をサポートしていることに注意してください)。これらの「エキゾチックな」型の関数の固定小数点を計算できる固定小数点コンビネーター (およびその実装!) について知りたいと思っています。無理数のようなものは無限の数列として 10 進数表現を持っているため、この計算は遅延評価する必要があるようです。これらの (推定上の) 遅延評価のいずれかで、真の不動点の適切な近似値が得られるでしょうか? 私のターゲット言語は Python と Clojure ですが、OCaml や Haskell の実装を見てもかまいません)。

私は何かについて混乱しています。不動点コンビネータを使用して、無限回の適用後に数学的に収束するシーケンスの不動点を評価する方法を示す例を (Clojure で) 生成したかったのですが、実際には有限回のステップ後に収束します。浮動小数点の有限精度に。ここで何かが足りないようです。

私はそれから得ることができます

このスタック オーバーフローがわかりません。より一般的には、私の以前の投稿に関連して、この方法でシーケンスの不動点を近似するために使用できる不動点コンビネーターの「正しい」バージョンを誰かが提示できるかどうか疑問に思っています。

F# を使用してラムダ計算を作成しています。私は現在、固定小数点演算子 (Y コンビネーターとも呼ばれます) を実装する方法を見つけようとして立ち往生しています。

それ以外は順調だと思います。式は、次の判別共用体で表されます。

私のeval機能はうまくいっているようです。次の例はすべて、期待どおりの結果をもたらします。
例 1:
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
例 2:
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
例 3:
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

しかし、前述したように、ラムダ計算内で固定小数点演算子を実装するのが困難です。ここでは次のように定義されています。
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

誰か提案はありますか？Yコンビネータに関する他の質問を見てきましたが、うまく採用できたものは見つかりませんでした。

すべての助けに感謝します。

編集：コードのタイプミスを修正しました...以前は、識別された組合のMult代わりに持っていました。Minusふと気がついたのがおかしい！

のドキュメンテーションに少し戸惑ったのでfix(現在は何をすべきかは理解できたと思いますが)、ソース コードを調べました。それは私をもっと混乱させました：

これはどのくらい正確に固定点を返しますか?

コマンドラインで試してみることにしました：

そして、それはそこにぶら下がっています。公平を期すために、これは私の古いMacbookにあり、少し遅いです。ただし、この関数は、id に渡されたものはすべて同じ結果を返すため、計算コストが高すぎることはありません(言うまでもなく、CPU 時間を消費しません)。私は何を間違っていますか？

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

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

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

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

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

可変アリティの多数の演算子の下でセットの固定小数点/閉包を計算するライブラリを探しています。例えば、

整数は、N (自然数、1..) のすべてを計算する必要があります。頑張って書いてみたのですが、足りないところがあります。これはあまり効率的ではありません。また、マルチアリティ関数の処理が最もエレガントではないと感じています。fixさらに、手動再帰の代わりに組み込み関数を使用して記述することは可能でしょうか?

例、

セットバージョン

これでパフォーマンスが大幅に向上するわけではありませんが、実際に高速化するには、計算を減らす方法を見つける必要があると思います。

怠惰なバージョンを設定する

私はRMonadこれを少しきれいにして、ダニエルが提案したように怠惰にしました。悲しいことに、ほとんどの時間は実際の乗算ルーチンに費やされていると思うので、この変更によるパフォーマンスの向上は見られませんでした。怠惰はクールだけど。

例

私は単項演算を失う必要がありましたが、それは取引キラーではありません。

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

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

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