不动点组合子
高阶函数y,其中y f = f (y f) / 維基百科,自由的 encyclopedia
親愛的 Wikiwand AI, 讓我們通過簡單地回答這些關鍵問題來保持簡短:
你能列出最重要的事實和統計數據嗎 不动点组合子?
為 10 歲的孩子總結這篇文章
顯示所有問題
不动点组合子(英語: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組合子允許一個匿名表達式來表示零或者甚至許多值,這在數理邏輯上是不一致的。