Y-コンビネーターの実践例

Question

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

私が見逃している、Y-Combinator の使用法に関するより実践的な例はありますか?実際の実稼働コードで実際に使用した人はいますか?それとも、Y-Combinator の使用は、本当に単に気が遠くなるような学術的な演習にすぎないのでしょうか (かなりクールな演習ではありますが)。

Answer 1

私は他の回答には同意しません。 固定小数点 (Y) コンビネータ する 実用的な用途がある, しかし、それらを見つけるには非常に想像力が必要です。ブルース・マクアダムみたいに。これが彼の論文の要約です 以上で終わりです:

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

それは素晴らしい紙です。関数型プログラミングに興味がある人は、おそらく楽しく読めるでしょう。

Answer 2

あなたはC＃でY Combinatorのを実装する上で、この気の利いた記事をチェックアウトすることができます：<のhref = "http://blogs.msdn.com/madst/archive/2007/05/11/recursive-lambda-expressions.aspx "REL =" nofollowをnoreferrer ">再帰的なラムダ式に、それはあなたがより良いアイデアを理解するのに役立つかもしれません。

あなたはウィキペディア上のいくつかの素晴らしい記事をチェックアウトすることもできます。不動点コンビネータをして< href = "http://en.wikipedia.org/wiki/Fixed-point_theorem#Fixed_point_theorems_in_discrete_mathematics_and_theoretical_computer_science" のrel = "nofollowをnoreferrer">

をポイント定理を修正> ネイサンが言うように、

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

Answer 3

あなたは非再帰的機能（=高階関数）によって記述され、あなたの関数を実行する仮想マシンとしてコンビネータと考えることができます。

時にはアスペクト指向プログラミング（memoizing、トレース、...）と同様のことを行うために、プログラム制御の下で、このコンビネータを持っていいだろうが、私の知っている何のプログラミング言語は、それを可能にしません。おそらくそれは、ほとんどの時間をすぎて扱いにくいおよび/または学ぶには余りにも難しいだろう。

Answer 4

私が間違っている場合は他の人は私を修正することができますが、私はYコンビネータは、厳密に学術的であるかなり確信しています。それについて考える：あなたの言語は高階関数ではなく、再帰をサポートしている必要があり、それを実装します。私はそのように知っている唯一の言語があります：。ラムダ計算は、

我々のマシンはチューリングマシンからラムダ計算上で実行されているに切り替えるまで、

ですから、Yコンビネータは厳密に学術的になります。

注：Yコンビネータに関連する他の機能技術のの便利なので、それを維持します。 Yコンビネータを理解することで、継続、遅延評価などを理解するのに役立ちます。

Answer 5

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が本当にそこに私を救いました。それは確かにかかわらず、心に来た最初のものではありませんでした。