Loading AI tools
高阶函数y,其中y f = f (y f) 来自维基百科,自由的百科全书
不动点组合子(英語:Fixed-point combinator,或不动点算子)是计算其他函数的一个不动点的高阶函数。
函数 f 的不动點是將函數應用在輸入值 x 時,會傳回與輸入值相同的值,使得 f(x) = x。例如,0 和 1 是函数 f(x) = x2 的不动点,因为 02 = 0 而 12 = 1。鉴于一阶函数(在简单值比如整数上的函数)的不动点是个一阶值,高阶函数 f 的不动点是另一个函数 g 使得 f(g) = g。那么,不动点算子 fix 的定義是
使得对于任何函数 f
不动点组合子它们可以用非递归的 lambda抽象来定义,在 lambda演算中的函數都是匿名的。然而在命令式編程語言中的遞歸,或許限制只能以呼叫函數名稱作為參數來實作。在函數式編程語言中的不动点,以 lambda抽象来定义的Y組合子為:
則允许匿名函数足夠逹成递归的作用,即递归函数。應用於帶有一個變量的函數,Y組合子通常不會終止。將 Y組合子應用於二或更多個變量的函數,會獲得更有趣的結果。第二個變量可當作計數器或索引。由此產生的函數行為,表現出如命令式語言中一個while
或for
迴圈。
這個組合子也是 Curry悖論的核心,演示了無型別的 lambda演算是一個不穩固的推論系統,因由 Y組合子允許一個匿名表達式來表示零或者甚至許多值,這在數理邏輯上是不一致的。
在无类型lambda演算中众所周知的(可能是最简单的)不动点组合子叫做Y组合子。它是Haskell B. Curry发现的,定义为
注意Y組合子意圖用于傳名求值策略,因為 (Y g)在傳值設置下會發散(對于任何g)。
在数学的特定形式化中,比如无类型lambda演算和组合演算中,所有表达式都被当作高阶函数。在这些形式化中,不动点组合子的存在性意味着“所有函数都至少有一个不动点”,函数可以有多于一个不同的不动点。
在其他系统中,比如简单类型lambda演算,不能写出有良好类型(well-typed)的不动点组合子。在这些系统中对递归的任何支持都必须明确的增加到语言中。带有扩展的递归数据类型的简单类型lambda演算,可以写出不动点算子,“有用的”不动点算子(它的应用总是会返回)的类型将是有限制的。
例如,在Standard ML中Y组合子的传值调用变体有类型∀a.∀b.((a→b)→(a→b))→(a→b),而传名调用变体有类型∀a.(a→a)→a。传名调用(正则序)变体在应用于传值调用的语言的时候将永远循环下去 -- 所有应用Y(f)展开为f(Y(f))。按传值调用语言的要求,到f的参数将接着展开,生成f(f(Y(f)))。这个过程永远重复下去(直到系统耗尽内存),而不会实际上求值f的主体。
考虑阶乘函数(使用邱奇数)。平常的递归数学等式
可以用lambda演算把这个递归的一个“单一步骤”表达为
这里的"f"是给阶乘函数的占位参数,用于传递给自身。 函数F进行求值递归公式中的一个单一步骤。 应用fix算子得到
Y组合子的可以在传值调用的应用序求值中使用的变体,由普通Y组合子的部分的η-展开给出:
Y组合子用SKI-演算表达为
另一个常见不动点组合子是图灵不动点组合子(阿兰·图灵发现的):
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.