Y コンビネーターは、物事の「機能」面からのコンピューター サイエンスの概念です。ほとんどのプログラマは、コンビネータについて聞いたことがあるとしても、コンビネータについてまったく知りません。
- Yコンビネータとは？
- コンビネータはどのように機能しますか?
- 彼らは何のために良いですか？
- それらは手続き型言語で役に立ちますか?
122000 次
18 に答える
304
Y コンビネータは、関数自体から参照できない場合に再帰を可能にする「関数型」(他の関数で動作する関数) です。コンピューター サイエンスの理論では、再帰を一般化し、その実装を抽象化することで、問題の関数の実際の作業から分離します。再帰関数のコンパイル時の名前を必要としないという利点は、一種のボーナスです。=)
これは、ラムダ関数をサポートする言語に適用されます。ラムダの式ベースの性質は、通常、名前で自分自身を参照できないことを意味します。そして、変数を宣言して参照し、ラムダを代入して自己参照ループを完了するという方法でこれを回避することは、脆弱です。ラムダ変数をコピーして、元の変数を再割り当てすると、自己参照が壊れます。
Y コンビネータは、静的型付け言語 (手続き型言語であることが多い) で実装するのが面倒で、多くの場合、使用するのが面倒です。通常、型付けの制限により、問題の関数の引数の数をコンパイル時に知る必要があるためです。これは、使用する必要があるすべての引数カウントに対して y コンビネータを作成する必要があることを意味します。
以下は、C# での Y-Combinator の使用方法と動作の例です。
Y コンビネータを使用すると、再帰関数を構築する「通常とは異なる」方法が必要になります。最初に、関数自体ではなく、既存の関数を呼び出すコードとして関数を記述する必要があります。
// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);
次に、それを呼び出す関数を受け取る関数に変換し、呼び出す関数を返します。これは関数と呼ばれます。これは、1 つの関数を取り、別の関数になる操作を実行するためです。
// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
(recurs) =>
(x) =>
x == 0 ? 1 : x * recurs(x - 1);
これで、関数を受け取り、階乗のように見える別の関数を返す関数ができましたが、それ自体を呼び出す代わりに、外側の関数に渡された引数を呼び出します。これをどのように階乗にしますか？内部関数をそれ自体に渡します。Y-Combinator は、再帰を導入できる永続的な名前を持つ関数であることにより、これを行います。
// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
return
t => // A function that...
F( // Calls the factorial creator, passing in...
Y(F) // The result of this same Y-combinator function call...
// (Here is where the recursion is introduced.)
)
(t); // And passes the argument into the work function.
}
階乗がそれ自体を呼び出すのではなく、階乗が階乗ジェネレーターを呼び出します (Y-Combinator への再帰呼び出しによって返されます)。t の現在の値に応じて、ジェネレーターから返された関数は、t - 1 でジェネレーターを再度呼び出すか、単に 1 を返し、再帰を終了します。
複雑で難解ですが、実行時にすべてが揺さぶられます。その機能の鍵は、「遅延実行」と、再帰を分割して 2 つの関数にまたがることです。内側の F は引数として渡され、必要な場合にのみ次の反復で呼び出されます。
于 2008-09-18T16:15:48.910 に答える
224
長文を読む準備ができている場合は、Mike Vanier が優れた説明を提供しています。簡単に言うと、必ずしもネイティブでサポートされていない言語で再帰を実装できます。
于 2008-09-18T15:23:03.500 に答える
111
数年前に書いた説明であるhttp://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.htmlからこれを取り上げました。
この例では JavaScript を使用しますが、他の多くの言語も同様に機能します。
私たちの目標は、1 変数の関数のみを使用し、代入を使用せず、名前で定義するなどして、1 変数の再帰関数を記述できるようにすることです (なぜこれが目標なのかは別の問題です。が与えられます。) 無理そうですよね？例として階乗を実装してみましょう。
ステップ 1 は、少しごまかすと、これは簡単にできるということです。2 変数の関数と代入を使用すると、再帰を設定するために代入を使用する必要が少なくとも回避できます。
// Here's the function that we want to recurse.
X = function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
};
// This will get X to recurse.
Y = function (builder, n) {
return builder(builder, n);
};
// Here it is in action.
Y(
X,
5
);
チートを減らすことができるかどうか見てみましょう。まず代入を使用していますが、その必要はありません。X と Y をインラインで記述できます。
// No assignment this time.
function (builder, n) {
return builder(builder, n);
}(
function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
},
5
);
しかし、2 変数の関数を使用して 1 変数の関数を取得しています。それを修正できますか？Haskell Curry という名の頭のいい人が巧妙なトリックを持っています。優れた高階関数があれば、必要なのは 1 つの変数の関数だけです。証拠は、次のような純粋に機械的なテキスト変換を使用して、2 つ (または一般的なケースではそれ以上) の変数の関数から 1 つの変数に取得できることです。
// Original
F = function (i, j) {
...
};
F(i,j);
// Transformed
F = function (i) { return function (j) {
...
}};
F(i)(j);
ここで ... まったく同じままです。(このトリックは、発明者にちなんで「カリー化」と呼ばれます。言語 Haskell は、Haskell Curry の名前でもあります。ファイルは役に立たない雑学の下にあります。) この変換をあらゆる場所に適用するだけで、最終的なバージョンが得られます。
// The dreaded Y-combinator in action!
function (builder) { return function (n) {
return builder(builder)(n);
}}(
function (recurse) { return function (n) {
if (0 == n)
return 1;
else
return n * recurse(recurse)(n - 1);
}})(
5
);
お気軽にお試しください。alert() が返されたら、それをボタンに結び付けます。このコードは、割り当て、宣言、または 2 つの変数の関数を使用せずに、階乗を再帰的に計算します。（しかし、それがどのように機能するかを追跡しようとすると、頭が回転する可能性があります。派生せずに、わずかに再フォーマットされたコードを扱うと、確実に困惑して混乱するコードになります。）
factorial を再帰的に定義する 4 行を、必要な他の再帰関数に置き換えることができます。
于 2011-07-15T21:39:20.197 に答える
89
これをゼロから構築しようとすることに何か意味があるのだろうか。どれどれ。基本的な再帰的階乗関数は次のとおりです。
function factorial(n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
fact計算自体を実行する代わりに、匿名の階乗計算関数を返すという新しい関数をリファクタリングして作成しましょう。
function fact() {
return function(n) {
return n == 0 ? 1 : n * fact()(n - 1);
};
}
var factorial = fact();
それは少し奇妙ですが、何も問題はありません。各ステップで新しい階乗関数を生成しているだけです。
この段階での再帰はまだかなり明白です。関数はfactそれ自体の名前を認識する必要があります。再帰呼び出しをパラメーター化してみましょう。
function fact(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
}
function recurser(x) {
return fact(recurser)(x);
}
var factorial = fact(recurser);
それは素晴らしいことですが、recurserそれでも自分の名前を知る必要があります。それもパラメータ化しましょう：
function recurser(f) {
return fact(function(x) {
return f(f)(x);
});
}
var factorial = recurser(recurser);
ここで、直接呼び出す代わりにrecurser(recurser)、結果を返すラッパー関数を作成しましょう。
function Y() {
return (function(f) {
return f(f);
})(recurser);
}
var factorial = Y();
recurserこれで、名前を完全に取り除くことができます。これはYの内部関数への単なる引数であり、関数自体に置き換えることができます。
function Y() {
return (function(f) {
return f(f);
})(function(f) {
return fact(function(x) {
return f(f)(x);
});
});
}
var factorial = Y();
まだ参照されている唯一の外部名はですがfact、これも簡単にパラメーター化できることは明らかであり、完全で一般的なソリューションを作成します。
function Y(le) {
return (function(f) {
return f(f);
})(function(f) {
return le(function(x) {
return f(f)(x);
});
});
}
var factorial = Y(function(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
});
于 2011-07-15T23:05:33.493 に答える
24
JavaScriptの y コンビネータ:
var Y = function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
};
var factorial = Y(function(recurse) {
return function(x) {
return x == 0 ? 1 : x * recurse(x-1);
};
});
factorial(5) // -> 120
編集：コードを見ることから多くのことを学びますが、これは背景がないと飲み込むのが少し難しいです-申し訳ありません。他の回答によって提示された一般的な知識があれば、何が起こっているのかを理解し始めることができます。
Y関数は「yコンビネータ」です。var factorialY が使用されている行を見てみましょう。recurse後で内部関数でも使用されるパラメーター (この例では ) を持つ関数を渡すことに注意してください。パラメーター名は基本的に内部関数の名前になり、再帰呼び出しを実行できるようになります (recurse()その定義で使用されるため)。 Y.
Y がどのように魔法を行うかについての完全な説明については、リンクされた記事をチェックしてください(私によるものではありません)。
于 2008-09-18T15:27:32.817 に答える
18
匿名再帰
fix固定小数点コンビネータは、定義により等価性を満たす高階関数です。
forall f. fix f = f (fix f)
fix fx固定小数点方程式の解を表す
x = f x
自然数の階乗は、次のように証明できます。
fact 0 = 1
fact n = n * fact (n - 1)
を使用するfixと、一般/μ-再帰関数に対する任意の構成的証明を、無名の自己参照なしで導き出すことができます。
fact n = (fix fact') n
どこ
fact' rec n = if n == 0
then 1
else n * rec (n - 1)
そのような
fact 3
= (fix fact') 3
= fact' (fix fact') 3
= if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
= 3 * (fix fact') 2
= 3 * fact' (fix fact') 2
= 3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
= 3 * 2 * (fix fact') 1
= 3 * 2 * fact' (fix fact') 1
= 3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
= 3 * 2 * 1 * (fix fact') 0
= 3 * 2 * 1 * fact' (fix fact') 0
= 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
= 3 * 2 * 1 * 1
= 6
この正式な証明は
fact 3 = 6
再書き込みに固定小数点コンビネータの同等性を系統的に使用する
fix fact' -> fact' (fix fact')
ラムダ計算
型指定されていないラムダ計算の形式は、文脈自由文法で構成されています
E ::= v Variable
| λ v. E Abstraction
| E E Application
ここで、変数の範囲は、ベータおよびイータ削減規則vとともに
(λ x. B) E -> B[x := E] Beta
λ x. E x -> E if x doesn’t occur free in E Eta
ベータ削減xは、抽象化 (「関数」) 本体内の変数のすべての自由発生をB式 (「引数」)に置き換えますE。Eta 削減により、冗長な抽象化が排除されます。公式から省略されることもあります。簡約規則が適用されない既約表現は、正規形または標準形です。
λ x y. E
の省略形です
λ x. λ y. E
(抽象化多元性)、
E F G
の省略形です
(E F) G
(アプリケーションの左結合性),
λ x. x
と
λ y. y
はアルファ相当です。
抽象化とアプリケーションは、ラムダ計算の 2 つの唯一の「言語プリミティブ」ですが、任意の複雑なデータと演算のエンコードを可能にします。
チャーチ数字は、ペアノの公理的自然数に似た自然数の符号化です。
0 = λ f x. x No application
1 = λ f x. f x One application
2 = λ f x. f (f x) Twofold
3 = λ f x. f (f (f x)) Threefold
. . .
SUCC = λ n f x. f (n f x) Successor
ADD = λ n m f x. n f (m f x) Addition
MULT = λ n m f x. n (m f) x Multiplication
. . .
という正式な証明
1 + 2 = 3
ベータ削減の書き換え規則を使用する:
ADD 1 2
= (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
= (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
= (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
= (λ m f x. f (m f x)) (λ h z. h (h z))
= λ f x. f ((λ h z. h (h z)) f x)
= λ f x. f ((λ z. f (f z)) x)
= λ f x. f (f (f x)) Normal form
= 3
コンビネーター
ラムダ計算では、コンビネータは自由変数を含まない抽象化です。最も単純には: I、恒等コンビネータ
λ x. x
恒等関数に同型
id x = x
このようなコンビネータは、SKI システムのようなコンビネータ計算の原始演算子です。
S = λ x y z. x z (y z)
K = λ x y. x
I = λ x. x
ベータ低下は強く正常化していません。すべての可約式「レデックス」がベータ簡約で正規形に収束するわけではありません。簡単な例は、オメガωコンビネータの発散アプリケーションです
λ x. x x
それ自体に:
(λ x. x x) (λ y. y y)
= (λ y. y y) (λ y. y y)
. . .
= _|_ Bottom
左端の部分式 (「頭」) の削減が優先されます。適用順序は置換の前に引数を正規化しますが、通常の順序はそうではありません。この 2 つの戦略は、熱心な評価 (C など) と遅延評価 (Haskell など) に似ています。
K (I a) (ω ω)
= (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))
熱心な適用次数ベータ削減の下で発散する
= (λ k l. k) a ((λ x. x x) (λ y. y y))
= (λ l. a) ((λ x. x x) (λ y. y y))
= (λ l. a) ((λ y. y y) (λ y. y y))
. . .
= _|_
厳密なセマンティクスで
forall f. f _|_ = _|_
しかし、怠惰な正規次数ベータ削減では収束します
= (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
= (λ l. a) ((λ x. x x) (λ y. y y))
= a
式が正規形を持っている場合、正規次数ベータ削減はそれを見つけます。
よ
固定小数点コンビネータの本質的な性質Y
λ f. (λ x. f (x x)) (λ x. f (x x))
によって与えられます
Y g
= (λ f. (λ x. f (x x)) (λ x. f (x x))) g
= (λ x. g (x x)) (λ x. g (x x)) = Y g
= g ((λ x. g (x x)) (λ x. g (x x))) = g (Y g)
= g (g ((λ x. g (x x)) (λ x. g (x x)))) = g (g (Y g))
. . . . . .
同等性
Y g = g (Y g)
に同形です
fix f = f (fix f)
型指定されていないラムダ計算は、一般/μ-再帰関数に対する任意の構成的証明をエンコードできます。
FACT = λ n. Y FACT' n
FACT' = λ rec n. if n == 0 then 1 else n * rec (n - 1)
FACT 3
= (λ n. Y FACT' n) 3
= Y FACT' 3
= FACT' (Y FACT') 3
= if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
= 3 * (Y FACT') (3 - 1)
= 3 * FACT' (Y FACT') 2
= 3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
= 3 * 2 * (Y FACT') 1
= 3 * 2 * FACT' (Y FACT') 1
= 3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
= 3 * 2 * 1 * (Y FACT') 0
= 3 * 2 * 1 * FACT' (Y FACT') 0
= 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
= 3 * 2 * 1 * 1
= 6
(掛け算遅れ、合流)
Churchian 型なしラムダ計算では、 以外に、再帰的に列挙可能な無限の固定小数点コンビネータが存在することが示されていますY。
X = λ f. (λ x. x x) (λ x. f (x x))
Y' = (λ x y. x y x) (λ y x. y (x y x))
Z = λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
Θ = (λ x y. y (x x y)) (λ x y. y (x x y))
. . .
正規次数のベータ簡約により、拡張されていない型指定されていないラムダ計算がチューリング完全な書き換えシステムになります。
Haskell では、固定小数点コンビネータをエレガントに実装できます。
fix :: forall t. (t -> t) -> t
fix f = f (fix f)
Haskell の遅延は、すべての部分式が評価される前に有限に正規化されます。
primes :: Integral t => [t]
primes = sieve [2 ..]
where
sieve = fix (\ rec (p : ns) ->
p : rec [n | n <- ns
, n `rem` p /= 0])
- David Turner:チャーチのテーゼと関数型プログラミング
- アロンゾ・チャーチ:初等整数論の解決不可能な問題
- ラムダ計算
- チャーチ・ロッサーの定理
于 2017-10-05T22:16:32.743 に答える
12
他の回答は、これに対する非常に簡潔な回答を提供しますが、1 つの重要な事実はありません。この複雑な方法で実用的な言語で固定小数点コンビネーターを実装する必要はなく、そうすることは実用的な目的にはなりません (「見て、私は Y コンビネーターを知っています」を除いて)。は"）。これは重要な理論的概念ですが、実用的な価値はほとんどありません。
于 2011-07-16T02:19:22.727 に答える
8
以下は、Y-Combinator と Factorial 関数の JavaScript 実装です (Douglas Crockford の記事から、http: //javascript.crockford.com/little.htmlで入手できます)。
function Y(le) {
return (function (f) {
return f(f);
}(function (f) {
return le(function (x) {
return f(f)(x);
});
}));
}
var factorial = Y(function (fac) {
return function (n) {
return n <= 2 ? n : n * fac(n - 1);
};
});
var number120 = factorial(5);
于 2010-12-27T05:28:32.577 に答える
6
Clojure と Scheme の両方で、Y-Combinator を理解するための一種の「ばかガイド」を書きました。彼らは「The Little Schemer」の題材に影響を受けています。
スキーム内: https://gist.github.com/z5h/238891
または Clojure: https://gist.github.com/z5h/5102747
どちらのチュートリアルもコメントが散りばめられたコードであり、お気に入りのエディターにカット アンド ペーストできます。
于 2009-07-03T03:05:25.580 に答える
3
y-combinatorは、匿名再帰を実装します。だから代わりに
function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }
できるよ
function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }
もちろん、y-combinatorは名前による呼び出し言語でのみ機能します。これを通常の値による呼び出し言語で使用する場合は、関連するz-combinatorが必要になります（y-combinatorは発散/無限ループになります）。
于 2011-07-16T03:37:43.623 に答える
3
固定小数点コンビネータ (または固定小数点演算子) は、他の関数の固定小数点を計算する高階関数です。この操作は、言語のランタイム エンジンからの明示的なサポートなしで、書き換え規則の形式で再帰の実装を許可するため、プログラミング言語理論に関連しています。（出典ウィキペディア）
于 2008-09-18T15:24:58.173 に答える
1
これに答える最善の方法は、JavaScript などの言語を選択することだと思います。
function factorial(num)
{
// If the number is less than 0, reject it.
if (num < 0) {
return -1;
}
// If the number is 0, its factorial is 1.
else if (num == 0) {
return 1;
}
// Otherwise, call this recursive procedure again.
else {
return (num * factorial(num - 1));
}
}
ここで、関数内で関数の名前を使用しないように書き直しますが、それでも再帰的に呼び出します。
関数名factorialが表示される唯一の場所は、呼び出しサイトです。
ヒント: 関数の名前は使用できませんが、パラメーターの名前は使用できます。
問題に取り組みます。調べないでください。これを解けば、y-combinator がどのような問題を解くのかが理解できます。
于 2016-07-23T21:09:24.280 に答える