40

私は最近関数型プログラミングについて少し読んでいて、Y-Combinatorを理解しようとしています。Y-Combinatorを使用して、再帰を直接サポートしていない言語で再帰を効果的に実装できることを理解しています。ただし、私が使用する可能性のあるすべての言語はすでに再帰をサポートしているため、そのためにY-Combinatorを使用することがどれほど役立つかはわかりません。

私が見逃しているY-Combinatorの使用法のより実用的な例はありますか？誰かが実際に実際の製品コードで使用したことがありますか？または、Y-Combinatorを使用しているのは、本当に気が遠くなるようなアカデミックなエクササイズです（かなりクールなエクササイズですが）。

4

5 に答える 5

27

他の回答には同意しません。固定小数点 (Y) コンビネータには実用的なアプリケーションがありますが、それらを見つけるには非常に想像力が必要です。ブルース・マクアダムのように。彼の論文That About Wraps it Upからの要約は次のとおりです。

固定小数点を計算するための Y コンビネータは、標準 ML で表現できます。これは、高階関数の力の例としてよく使用されますが、一般的に有用なプログラミング構造とは見なされていません。ここでは、Y コンビネータとラッパーに基づくプログラミング手法を使用して、コードを書き直して再コンパイルしなければ、関数の内部動作をある程度制御できるようにする方法を説明します。実験として、この手法を使用して型推論アルゴリズム W を実装し、アルゴリズムへの干渉を最小限に抑えてエラー メッセージが生成されるようにします。このサンプル プログラムのコードは、概念の真の有用性と適用の容易さを示しています。他の多くの実装手法と可能なアプリケーションについても説明します。

これは素晴らしい論文です。関数型プログラミングに興味のある人なら誰でも、きっと楽しく読めるでしょう。

于 2009-05-16T00:43:02.947 に答える
7

Y CombinatorのC＃での実装に関するこの気の利いた投稿をチェックしてください：再帰的なラムダ式、それはあなたがアイデアをよりよく理解するのを助けるかもしれません。

ウィキペディアのいくつかの素晴らしい記事をチェックすることをお勧めします：不動点コンビネータと不動点定理

Nathanが言うように、多くの機能技術はYコンビネータに関連していて便利なので、それを維持してください。Yはコードをよりよく理解できるので本当に便利ですが、それがどのように役立つかを説明するのに特に役立つとは思いません。

于 2009-05-15T17:22:22.520 に答える
4

コンビネータは、関数を実行する仮想マシンと考えることができます。これは、非再帰関数（=高階関数）で記述されます。

アスペクト指向プログラミング（メモ化、トレースなど）と同様のことを行うために、このコンビネータをプログラム制御下に置くと便利な場合がありますが、私が知っているプログラミング言語では許可されていません。おそらく、ほとんどの場合、面倒であるか、学習するのが難しいでしょう。

于 2009-05-15T17:14:52.773 に答える
4

私が間違っている場合は他の人が訂正してくれますが、Y コンビネータは厳密にアカデミックなものであると確信しています。考えてみてください: それを実装するには、言語は高階関数をサポートする必要がありますが、再帰はサポートしません。私がそのように知っている言語は 1 つだけです: ラムダ計算です。

したがって、マシンがチューリング マシンからラムダ計算で実行されるように切り替わるまで、Y コンビネーターは厳密に学術的なものになります。

注: Y コンビネータに関連する他の機能的な手法は便利なので、そのままにしておいてください。Y コンビネータを理解すると、継続や遅延評価などを理解するのに役立ちます。

于 2009-05-15T16:11:24.843 に答える
2 
let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

これは、私が F# で作成している小さなゲーム ライブラリのコンパイラの例です。より具体的には、上記で sprites_up を再帰的に呼び出す必要があります。そうしないと、インデント パーサーが正しく機能しません。

Y Combinator がなければ、パーサーを適切に実行できず、次のようなものを書く必要があったでしょう。

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x)

Y Combinator は本当に私を救ってくれました。しかし、それは確かに最初に頭に浮かんだことではありませんでした。

于 2016-02-14T10:13:57.487 に答える