函数式编程 - 什么是Y-combinator?

Y-combinator是一种来自事物“功能”方面的计算机科学概念。 大多数程序员对组合器一无所知,如果他们甚至听说过它们的话。

  • 什么是Y-combinator?
  • 组合器如何工作?
  • 它们有什么用?
  • 它们在程序语言中有用吗?
18个解决方案
275 votes

Y-combinator是一个“功能”(对其他函数起作用的函数),当你无法从内部引用函数时,它会启用递归。 在计算机科学理论中,它概括了递归,抽象了它的实现,从而将它与所讨论的函数的实际工作分开。 不需要递归函数的编译时名称的好处是一种奖励。=)

这适用于支持lambda函数的语言。 基于表达的lambdas本质通常意味着他们不能通过名字来引用自己。 通过声明变量,引用它,然后将lambda分配给它来完成自引用循环来解决这个问题是很脆弱的。 可以复制lambda变量,并重新分配原始变量,这会破坏自引用。

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);

然后将其转换为一个函数,它接受一个函数来调用,并返回一个执行此操作的函数。 这称为功能,因为它需要一个函数,并执行一个操作,导致另一个函数。

// 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作为参数传递,仅在必要时才在下一次迭代中调用。

Chris Ammerman answered 2019-01-28T21:44:27Z
187 votes

如果你准备好长时间阅读,Mike Vanier有一个很好的解释。 简而言之,它允许您使用一种本身不一定支持它的语言来实现递归。

Nicholas Mancuso answered 2019-01-28T21:43:09Z
96 votes

我已经从[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个变量的函数。 (但试图追踪它是如何工作的可能会让你头晕目眩。并且在没有推导的情况下处理它,只是稍微重新格式化将导致代码肯定会困惑和混淆。)

您可以替换递归定义阶乘的4行你想要的任何其他递归函数。

btilly answered 2019-01-28T21:45:45Z
78 votes

我想知道从头开始构建这个是否有任何用处。 让我们来看看。 这是一个基本的递归因子函数:

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);

这很好,但fact仍然需要知道自己的名字。 我们也要参数化:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

现在,让我们创建一个返回其结果的包装函数,而不是直接调用fact

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

我们现在可以完全摆脱fact的名称; 它只是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);
    };
});
Wayne Burkett answered 2019-01-28T21:46:54Z
45 votes

上面的大多数答案都描述了Y-combinator是什么,但不是它的用途。

固定点组合器用于表明lambda演算是完整的。 这是计算理论中非常重要的结果,为函数式编程提供了理论基础。

学习定点组合器也帮助我真正理解函数式编程。 我在实际编程中从未发现它们有任何用处。

Jørgen Fogh answered 2019-01-28T21:47:30Z
23 votes

JavaScript中的y-combinator:

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组合子”。 现在看一下使用Y的var factorial行。 请注意,您将一个函数传递给它,该函数具有一个参数(在本例中为recurse),该参数稍后也会在内部函数中使用。 参数名称基本上成为内部函数的名称,允许它执行递归调用(因为它在其定义中使用recurse()。)y-combinator执行将其他匿名内部函数与传递的函数的参数名称相关联的魔力。 到Y.

有关Y如何完成魔法的完整解释,请查看链接的文章(不是我的btw)。

Zach answered 2019-01-28T21:48:12Z
16 votes

对于那些没有深入体验过函数式编程的程序员而言,现在并不关心,但是有点好奇:

Y组合子是一个公式,它允许您在函数不能具有名称但可以作为参数传递,用作返回值并在其他函数中定义的情况下实现递归。

它通过将函数作为参数传递给自身来工作,因此它可以调用自身。

它是lambda演算的一部分,它实际上是数学,但实际上是一种编程语言,对于计算机科学尤其是函数式编程来说是非常基础的。

Y组合器的日常实用价值是有限的,因为编程语言倾向于让您命名功能。

如果您需要在警察阵容中识别它,它看起来像这样:

Y =λf。(λx.f(x x))(λx.f(x x))

由于重复λ,您通常可以发现它。

λ符号是希腊字母lambda,它给lambda演算起了名字,并且有很多(λx.t)样式术语,因为这就是lambda演算的样子。

El Zorko answered 2019-01-28T21:49:28Z
12 votes

其他答案提供了非常简洁的答案,没有一个重要的事实:你不需要用这种复杂的方式用任何实用语言实现定点组合器,这样做没有实际意义(除了“看,我知道Y-combinator是什么)是“)。 这是重要的理论概念,但没有什么实际价值。

Ales Hakl answered 2019-01-28T21:49:51Z
6 votes

这是Y-Combinator和Factorial函数的JavaScript实现(来自Douglas Crockford的文章,可在以下网站获得:http:// 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);
xgMz answered 2019-01-28T21:50:13Z
6 votes

Y-Combinator是磁通电容器的另一个名称。

Jon Davis answered 2019-01-28T21:50:35Z
5 votes

我在Clojure和Scheme中为Y-Combinator写了一篇“白痴指南”,以帮助自己掌握它。 他们受到“The Little Schemer”中材料的影响

在Scheme中:[https://gist.github.com/z5h/238891]

或者Clojure:[https://gist.github.com/z5h/5102747]

这两个教程都是插入注释的代码,应该剪切和放大。 可以进入你最喜欢的编辑器。

z5h answered 2019-01-28T21:51:17Z
4 votes

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将发散/无限循环)。

Andrew answered 2019-01-28T21:51:47Z
4 votes

匿名递归

定点组合器是高阶函数Y,根据定义满足等价

forall f.  fix f  =  f (fix f)

Y表示定点方程B的解

               x  =  f x

自然数的阶乘可以通过证明

fact 0 = 1
fact n = n * fact (n - 1)

使用Y,可以导出关于通用/μ递归函数的任意构造性证明而没有非自然的自引用性。

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演算

无类型的lambda演算形式主义包含无上下文语法

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

其中Y是变量的范围,以及beta和eta减少规则

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

Beta缩减通过表达式(“argument”)E替换抽象(“function”)体B中变量Y的所有自由出现.Eta缩减消除了冗余抽象。 形式主义有时会省略它。 不适用缩减规则的不可简化表达是正常或规范形式。

λ x y. E

是简写

λ x. λ y. E

(抽象多元化),

E F G

是简写

(E F) G

(申请左关联),

λ x. x

λ y. y

是α等价的。

抽象和应用是lambda演算的两个唯一“语言基元”,但它们允许编码任意复杂的数据和操作。

教会数字是与Peano-axiomatic naturals类似的自然数字的编码。

   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演算中,组合器是不包含自由变量的抽象。 最简单:Y,身份组合

λ x. x

与身份功能同构

id x = x

这种组合器是组合器结石的原始算子,如SKI系统。

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

Beta减少并没有强烈正常化; 并非所有可简化的表达式,“重新索引”,在β减少下收敛到正常形式。 一个简单的例子是omega Y组合器的不同应用

λ x. x x

对自己:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

减少最左边的子表达(“头部”)是优先的。 应用顺序在替换之前规范化参数,而正常顺序则不规则化。 这两种策略类似于急切的评估,例如: C和懒惰评估,例如哈斯克尔。

   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)

无类型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

(乘法延迟,汇合)

对于Churchian无类型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))
  . . .

正常的β阶减少使得未扩展的无类型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])

  • 大卫特纳:教会的论文和功能编程
  • 阿隆佐教会:一个无法解决的基本数论问题
  • Lambda演算
  • Church-Rosser定理
answered 2019-01-28T21:57:05Z
3 votes

定点组合器(或定点算子)是一个高阶函数,用于计算其他函数的固定点。 此操作与编程语言理论相关,因为它允许以重写规则的形式实现递归,而无需语言的运行时引擎的明确支持。 (src维基百科)

Thomas Wagner answered 2019-01-28T21:57:28Z
3 votes

这个操作员可以简化你的生活:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

然后你避免额外的功能:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

最后,请致电fac(5)

Tires answered 2019-01-28T21:58:02Z
2 votes

作为组合者的新手,我发现Mike Vanier的文章(感谢Nicholas Mancuso)真的很有帮助。 我想写一个总结,除了记录我的理解之外,如果它对其他人有帮助我会很高兴。

从蹩脚到蹩脚

以阶乘为例,我们使用以下almost-factorial函数计算阶乘数(Y f)

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

在上面的伪代码中,(Y f)接收功能f和编号frfr是curry,因此可以看作是接收功能x并返回1-arity功能)。

(Y f)计算f的阶乘时,它将fr的阶乘计算委托给函数fr,并将该结果累加到x(在这种情况下,它将(x - 1)的结果与x相乘)。

它可以被视为(Y f)采用一个蹩脚的阶乘函数版本(只能计算到数字f)并返回一个不太蹩脚的阶乘版本(计算直到编号fr)。 如以这种形式:

almost-factorial crappy-f = less-crappy-f

如果我们反复将不太糟糕的factorial版本传递给(Y f),我们最终会获得所需的阶乘函数f。它可以被认为是:

almost-factorial f = f

固定点

(Y f)表示f的事实是功能fr的定点。

这是一种非常有趣的方式来看到上述功能的关系,这对我来说是一个很好的时刻。 (如果你没有,请阅读Mike关于修复点的帖子)

三个功能

为了概括,我们有一个非递归函数(Y f)(就像我们的几乎因子),我们有它的定点函数f(就像我们的f),然后fr做的是当你给fr x,Y返回定点 功能fn

所以总结(假设(Y f)只采用一个参数; f退化为frfr ...递归):

  • 我们将核心计算定义为(Y f)(Y f),这是几乎有用的功能 - 虽然我们不能直接在fr上使用f,但它很快就会有用。 这个非递归fr使用函数x来计算其结果
  • (Y f),(Y f)f的固定点,fr是有用的功能,我们可以使用fr获取x获得我们的结果
  • (Y f),(Y f)返回函数的定点,f将我们几乎有用的函数(Y f)转换为有用的f

派生(Y f)(不包括在内)

我将跳过(Y f)的推导并转到理解f.Mike Vainer的帖子有很多细节。

形式为(Y f)

(Y f)定义为(以lambda演算格式):

Y f = λs.(f (s s)) λs.(f (s s))

如果我们替换函数左侧的变量(Y f),我们得到

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

确实,(Y f)的结果是f的定点。

为什么(Y f)可以使用?

根据Y的签名,fn可以是任何arity的函数,为简化起见,我们假设Y只接受一个参数,如我们的阶乘函数。

def fn fr x = accumulate x (fr (- x 1))

Y开始,我们继续

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

当最内层Y是基本情况且fn在计算中不使用Y时,递归计算终止。

再次看Y

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

所以

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

对我来说,这个设置的神奇部分是:

  • Yfn相互依赖相互:Y“包裹”fr内,每次fn用于计算x,它的产卵'(?“升降机”)的fn和代表计算到fn(通过本身frx); 另一方面,fn取决于fr并使用fr来计算较小问题的结果x-1
  • 当时Y用于定义fn(当Y在其操作中使用fr时),尚未定义真实fn
  • 它是Y,它定义了真正的业务逻辑。 基于fn,Y创建fr - 特定形式的辅助函数 - 以便于以递归方式计算fn

这帮助我理解Y此刻,希望有所帮助。

顺便说一下,我还发现了“通过Lambda微积分进行功能编程简介”这本书非常好,我只是通过它而且我无法理解书中的Y这一事实让我想到了这篇文章。

Dapeng Li answered 2019-01-28T22:02:02Z
2 votes

以下是原始问题的答案,这些问题是根据Nicholas Mancuso的答案中提到的文章(TOTALY值得一读)编写的,以及其他答案:

什么是Y-combinator?

Y-combinator是一个“函数”(或一个高阶函数 - 一个对其他函数起作用的函数),它接受一个参数,这是一个不递归的函数,并返回一个函数的版本,递归。


有些递归=),但更深入的定义:

组合子 - 只是一个没有自由变量的lambda表达式。
自由变量 - 是一个不是绑定变量的变量。
绑定变量 - 包含在lambda表达式主体内部的变量,该表达式将变量名称作为其参数之一。

考虑这个问题的另一种方法是组合器就是这样一个lambda表达式,在这个表达式中,你能够用它的定义替换组合器的名称到处找到它并且一切都仍然有效(如果组合器将会进入无限循环) 在lambda体内包含对自身的引用。

Y-combinator是一个定点组合器。

函数的固定点是函数域的一个元素,由函数映射到自身。
也就是说,c是函数f(x)的固定点,如果f(c) = c
这意味着f(f(...f(c)...)) = fn(c) = c

组合器如何工作?

下面的示例假设强+动态类型:

懒惰(正常顺序)Y组合子:
此定义适用于具有延迟(也称为延迟,按需调用)评估的语言 - 评估策略将表达式的评估延迟到需要它的值。

Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

这意味着,对于给定函数λ(其是非递归函数),可以首先通过计算λx.f(x x)获得相应的递归函数,然后将该lambda表达式应用于其自身。

严格(应用订单)Y-combinator:
此定义适用于具有严格(也是:急切,贪婪)评估的语言 - 评估策略,其中表达式在绑定到变量后立即进行评估。

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

它与它本质上的懒惰一样,只是有一个额外的λ包装来延迟lambda的身体评估。 我问过另一个问题,与这个话题有些相关。

它们有什么用?

从Chris Ammerman的回答中借来的被盗:Y-combinator概括了递归,抽象了它的实现,从而将它与所讨论的函数的实际工作分开。

尽管Y-combinator具有一些实际应用,但它主要是一个理论概念,理解它将扩展您的整体愿景,并且可能会提高您的分析和开发人员技能。

它们在程序语言中有用吗?

如Mike Vanier所述:可以用许多静态类型语言定义Y组合子,但是(至少在我看过的例子中)这样的定义通常需要一些非显而易见的类型hackery,因为Y组合子本身并不是' t有一个简单的静态类型。 这超出了本文的范围,所以我不会进一步提及它

正如Chris Ammerman所说:大多数过程语言都有静态类型。

所以回答这个 - 不是真的。

Filipp W. answered 2019-01-28T22:04:58Z
0 votes

我认为回答这个问题的最好方法是选择一种语言,比如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解决了什么问题。

zumalifeguard answered 2019-01-28T22:05:46Z
translate from https://stackoverflow.com:/questions/93526/what-is-a-y-combinator