从“函数”的角度来看，y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子，如果他们听说过的话。
什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?
当前回答
我从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html中引用了这个，这是我几年前写的一个解释。
在本例中我将使用JavaScript，但许多其他语言也可以。
我们的目标是写出一个1的递归函数 变量只使用1变量的函数，没有 赋值，通过名称定义事物等(为什么这是我们的 目标是另一个问题，我们把它作为 我们所面临的挑战。)似乎不可能，是吧?作为 举个例子，让我们实现阶乘。
第一步是说我们可以很容易地做到这一点，如果我们 作弊了一点。使用二元函数和 我们至少可以避免使用 赋值来建立递归。
// 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
);
但是我们用两个变量的函数来得到一个1的函数 变量。我们能解决这个问题吗?一个叫 Haskell Curry有一个巧妙的技巧，如果你有好的高阶 那么你只需要一个变量的函数。的 证明是你可以从函数2(或更多) 一般情况下)变量以1变量为纯粹 像这样的机械文本转换:
// Original
F = function (i, j) {
...
};
F(i,j);
// Transformed
F = function (i) { return function (j) {
...
}};
F(i)(j);
在那里……完全一样。(这个技巧叫做 “模仿”它的发明者。Haskell也是一种语言 以哈斯克尔·库里命名。把它归为无用的琐事。) 现在只要把这个变换应用到任何地方，我们就得到 我们的最终版本。
// 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变量的赋值、声明或函数。(但 试图追踪它是如何工作的可能会让你头晕目眩。 递过来，没有推导，只是稍微重新格式化了一下 会导致代码令人困惑。)
可以将递归定义阶乘的4行替换为 任何你想要的递归函数。
其他回答
我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:
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();
这有点奇怪，但这没什么问题。我们只是在每一步生成一个新的阶乘函数。
这个阶段的递归仍然相当明确。事实函数需要知道自己的名字。让我们参数化递归调用:
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);
这很好，但是递归仍然需要知道自己的名字。让我们把它参数化:
function recurser(f) {
return fact(function(x) {
return f(f)(x);
});
}
var factorial = recurser(recurser);
现在，我们不直接调用递归器(recurser)，而是创建一个包装器函数，返回它的结果:
function Y() {
return (function(f) {
return f(f);
})(recurser);
}
var factorial = Y();
现在我们可以完全去掉递归的名字;它只是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);
};
});
对于那些没有深入接触过函数式编程，现在也不想开始，但有点好奇的程序员:
Y组合子是一个公式，它允许你在这样的情况下实现递归:函数不能有名称，但可以作为参数传递，用作返回值，并在其他函数中定义。
它的工作原理是将函数作为参数传递给自己，这样它就可以调用自己。
它是lambda演算的一部分，lambda演算实际上是数学，但实际上是一种编程语言，是计算机科学尤其是函数式编程的基础。
Y组合子的日常实用价值是有限的，因为编程语言倾向于让你命名函数。
如果你需要在警察的队列中识别它，它看起来是这样的:
Y = λf.(λx。F (x x)) (λx。F (x x))
你通常可以发现它，因为重复的(λx。F (x x))
λ符号是希腊字母，这是λ演算的名字，有很多(λx.t)风格的术语因为这就是λ演算的样子。
Y-combinator是一个“函数”(一个作用于其他函数的函数)，当你不能从内部引用函数时，它可以实现递归。在计算机科学理论中，它概括了递归，抽象了递归的实现，从而将递归与函数的实际工作分离开来。递归函数不需要编译时名称的好处是一种额外的好处。=）
这适用于支持lambda函数的语言。lambdas基于表达式的特性通常意味着它们不能通过名称引用自己。通过声明变量，引用它，然后赋值给它，来完成自引用循环，是很脆弱的。可以复制lambda变量，并重新分配原始变量，这将破坏自引用。
y组合子在静态类型语言(过程性语言通常如此)中实现起来很麻烦，而且经常使用起来也很麻烦，因为通常类型限制要求在编译时知道函数的参数数量。这意味着必须为需要使用的任何参数count编写y-combinator。
下面是一个在c#中如何使用和工作的Y-Combinator的例子。
使用y组合子涉及到一种构造递归函数的“不寻常”方式。首先，你必须把你的函数写成一段代码，调用一个已经存在的函数，而不是它自己:
// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 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，终止递归。
它是复杂而神秘的，但在运行时，它的工作关键是“延迟执行”，并将递归分解为跨越两个函数。内部的F作为参数传递，仅在必要时才在下一次迭代中调用。
我从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html中引用了这个，这是我几年前写的一个解释。
在本例中我将使用JavaScript，但许多其他语言也可以。
我们的目标是写出一个1的递归函数 变量只使用1变量的函数，没有 赋值，通过名称定义事物等(为什么这是我们的 目标是另一个问题，我们把它作为 我们所面临的挑战。)似乎不可能，是吧?作为 举个例子，让我们实现阶乘。
第一步是说我们可以很容易地做到这一点，如果我们 作弊了一点。使用二元函数和 我们至少可以避免使用 赋值来建立递归。
// 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
);
但是我们用两个变量的函数来得到一个1的函数 变量。我们能解决这个问题吗?一个叫 Haskell Curry有一个巧妙的技巧，如果你有好的高阶 那么你只需要一个变量的函数。的 证明是你可以从函数2(或更多) 一般情况下)变量以1变量为纯粹 像这样的机械文本转换:
// Original
F = function (i, j) {
...
};
F(i,j);
// Transformed
F = function (i) { return function (j) {
...
}};
F(i)(j);
在那里……完全一样。(这个技巧叫做 “模仿”它的发明者。Haskell也是一种语言 以哈斯克尔·库里命名。把它归为无用的琐事。) 现在只要把这个变换应用到任何地方，我们就得到 我们的最终版本。
// 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变量的赋值、声明或函数。(但 试图追踪它是如何工作的可能会让你头晕目眩。 递过来，没有推导，只是稍微重新格式化了一下 会导致代码令人困惑。)
可以将递归定义阶乘的4行替换为 任何你想要的递归函数。
匿名的递归
定点组合子是一种根据定义满足等价的高阶函数固定
forall f. fix f = f (fix f)
固定f表示定点方程x的解
x = f x
自然数的阶乘可以用
fact 0 = 1
fact n = n * fact (n - 1)
在一般/μ-递归函数上使用固定的、任意的构造证明可以在没有匿名自指性的情况下导出。
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')
微积分
无类型lambda演算形式主义包含在上下文无关的语法中
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
Beta约简用表达式(“参数”)e替换抽象(“函数”)体B中变量x的所有自由出现。Eta约简消除了冗余抽象。它有时在形式主义中被省略。不适用约简规则的不可约表达式是正常形式或规范形式。
λ x y. E
是简写
λ x. λ y. E
(抽象multiarity),
E F G
是简写
(E F) G
(应用程序left-associativity),
λ x. x
and
λ y. y
alpha-equivalent。
抽象和应用是lambda演算中仅有的两个“语言原语”，但它们允许对任意复杂的数据和操作进行编码。
教会数字是一种自然数的编码，类似于花生公理化自然数。
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
使用beta约简重写规则:
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
组合子
在lambda微积分中，组合子是不包含自由变量的抽象。最简单的，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
减少最左边的子表达式(“头”)是优先的。应用顺序在替换前规范化参数，常规顺序则不然。这两种策略类似于渴望求值(例如C)和懒惰求值(例如Haskell)。
K (I a) (ω ω)
= (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))
在热切应用阶beta缩减下发散
= (λ 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
如果一个表达式具有正规形式，则用正规阶beta缩减法可以找到它。
Y
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)
无类型lambda演算可以在一般/μ递归函数上编码任意构造证明。
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
(乘法延迟，汇流)
对于丘奇无类型lambda演算，除了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))
. . .
法阶beta约简使未扩展的无类型lambda演算成为一个图灵完全重写系统。
在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])
大卫·特纳:丘奇的论文和函数式编程 阿朗佐·丘奇:初等数论的一个不可解问题 微积分 Church-Rosser定理
推荐文章
- 如何在PostgreSQL中查看视图的CREATE VIEW代码?
- 面向对象编程，函数式编程，过程式编程
- 什么是“P=NP?”，为什么这是一个如此著名的问题?
- 为什么不可变性在JavaScript中如此重要(或需要)?
- 如何使用underscore.js作为模板引擎?
- Scala中的“提升”是什么?
- Javascript相当于Python的zip函数
- 使用array_map()访问第一级键，而不调用' array_keys() '
- 给物体加水是什么意思?
- functools partial是怎么做的呢?
- 过程式编程和函数式编程的区别是什么?
- 没有可变状态，你怎么能做任何有用的事情?
- 什么是循环不变量?
- 如何在Python中使用lambda排序
- 什么是弱头正常形式?
