U组合子
通过将函数作为参数传递给自身,函数可以使用其参数而不是名称来递归!所以给定的函数U
应该至少有一个参数可以绑定到函数(本身)。
在下面的例子中,我们没有退出条件,所以我们将无限循环直到发生堆栈溢出
const U = f => f (f) // call function f with itself as an argument
U (f => (console.log ('stack overflow imminent!'), U (f)))
我们可以使用多种技术来停止无限递归。在这里,我将编写匿名函数以返回另一个等待输入的匿名函数;在这种情况下,一些数字。当提供一个数字时,如果它大于0,我们将继续重复,否则返回0。
const log = x => (console.log (x), x)
const U = f => f (f)
// when our function is applied to itself, we get the inner function back
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
// returns: (x => x > 0 ? U (f) (log (x - 1)) : 0)
// where f is a reference to our outer function
// watch when we apply an argument to this function, eg 5
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0) (5)
// 4 3 2 1 0
这里不是很明显的是,当我们的函数第一次使用U
组合子应用于自身时,它返回一个等待第一个输入的函数。如果我们给它起个名字,就可以有效地使用 lambdas(匿名函数)构造递归函数
const log = x => (console.log (x), x)
const U = f => f (f)
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
countDown (5)
// 4 3 2 1 0
countDown (3)
// 2 1 0
只是这不是直接递归——一个使用自己的名字调用自己的函数。我们的定义countDown
没有在其主体内部引用自身,并且仍然可以递归
// direct recursion references itself by name
const loop = (params) => {
if (condition)
return someValue
else
// loop references itself to recur...
return loop (adjustedParams)
}
// U combinator does not need a named reference
// no reference to `countDown` inside countDown's definition
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
如何使用 U 组合器从现有函数中删除自引用
在这里,我将向您展示如何将使用对自身的引用的递归函数更改为使用 U 组合子来代替自引用的函数
const factorial = x =>
x === 0 ? 1 : x * factorial (x - 1)
console.log (factorial (5)) // 120
现在使用 U 组合器替换内部引用 factorial
const U = f => f (f)
const factorial = U (f => x =>
x === 0 ? 1 : x * U (f) (x - 1))
console.log (factorial (5)) // 120
基本的替换模式是这样的。记下,我们将在下一节中使用类似的策略
// self reference recursion
const foo = x => ... foo (nextX) ...
// remove self reference with U combinator
const foo = U (f => x => ... U (f) (nextX) ...)
Y组合子
相关:U 和 Y 组合子使用镜像类比解释
在上一节中,我们看到了如何使用 U 组合子将自引用递归转换为不依赖于命名函数的递归函数。必须记住始终将函数作为第一个参数传递给自身,这有点令人烦恼。嗯,Y-combinator 建立在 U-combinator 的基础上,去掉了那个乏味的部分。这是一件好事,因为消除/降低复杂性是我们制作函数的主要原因
首先,让我们推导出我们自己的 Y 组合器
// standard definition
const Y = f => f (Y (f))
// prevent immediate infinite recursion in applicative order language (JS)
const Y = f => f (x => Y (f) (x))
// remove reference to self using U combinator
const Y = U (h => f => f (x => U (h) (f) (x)))
现在我们将看看它的用法与 U-combinator 相比如何。注意,要重复,U (f)
我们可以简单地调用f ()
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
Y (f => (console.log ('stack overflow imminent!'), f ()))
现在我将countDown
使用该程序进行演示Y
- 您会看到这些程序几乎相同,但 Y 组合器使事情更简洁
const log = x => (console.log (x), x)
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const countDown = Y (f => x => x > 0 ? f (log (x - 1)) : 0)
countDown (5)
// 4 3 2 1 0
countDown (3)
// 2 1 0
现在,我们可以看到factorial
,以及
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const factorial = Y (f => x =>
x === 0 ? 1 : x * f (x - 1))
console.log (factorial (5)) // 120
如您所见,f
成为递归机制本身。为了重现,我们将其称为普通函数。我们可以用不同的参数多次调用它,结果仍然是正确的。并且因为它是一个普通的函数参数,我们可以随意命名它,比如recur
下面——
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const fibonacci = Y (recur => n =>
n < 2 ? n : recur (n - 1) + (n - 2))
console.log (fibonacci (10)) // 55
具有 1 个以上参数的 U 和 Y 组合器
在上面的例子中,我们看到了如何循环并传递参数来跟踪计算的“状态”。但是如果我们需要跟踪额外的状态呢?
我们可以使用像数组这样的复合数据……
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const fibonacci = Y (f => ([a, b, x]) =>
x === 0 ? a : f ([b, a + b, x - 1]))
// starting with 0 and 1, generate the 7th number in the sequence
console.log (fibonacci ([0, 1, 7]))
// 0 1 1 2 3 5 8 13
但这很糟糕,因为它暴露了内部状态(计数器a
和b
)。如果我们能打电话fibonacci (7)
得到我们想要的答案,那就太好了。
使用我们对柯里化函数(一元(1 参数)函数的序列)的了解,我们可以轻松实现我们的目标,而无需修改Y
或依赖复合数据或高级语言功能的定义。
fibonacci
仔细看看下面的定义。我们立即申请0
and 1
which 分别绑定到a
和b
。现在斐波那契只是等待提供最后一个参数,该参数将绑定到x
。当我们递归时,我们必须调用f (a) (b) (x)
(not f (a,b,x)
),因为我们的函数是柯里化的。
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const fibonacci = Y (f => a => b => x =>
x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
console.log (fibonacci (7))
// 0 1 1 2 3 5 8 13
这种模式可用于定义各种函数。下面我们将看到使用定义的两个函数Y
组合子(range
和reduce
)和衍生物reduce
,map
。
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const range = Y (f => acc => min => max =>
min > max ? acc : f ([...acc, min]) (min + 1) (max)) ([])
const reduce = Y (f => g => y => ([x,...xs]) =>
x === undefined ? y : f (g) (g (y) (x)) (xs))
const map = f =>
reduce (ys => x => [...ys, f (x)]) ([])
const add = x => y => x + y
const sq = x => x * x
console.log (range (-2) (2))
// [ -2, -1, 0, 1, 2 ]
console.log (reduce (add) (0) ([1,2,3,4]))
// 10
console.log (map (sq) ([1,2,3,4]))
// [ 1, 4, 9, 16 ]
这都是匿名的 OMG
因为我们在这里使用纯函数,所以我们可以用任何命名函数替换它的定义。观察当我们使用斐波那契数并用它们的表达式替换命名函数时会发生什么
/* const U = f => f (f)
*
* const Y = U (h => f => f (x => U (h) (f) (x)))
*
* const fibonacci = Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
*
*/
/*
* given fibonacci (7)
*
* replace fibonacci with its definition
* Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
*
* replace Y with its definition
* U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
//
* replace U with its definition
* (f => f (f)) U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
*/
let result =
(f => f (f)) (h => f => f (x => h (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
console.log (result) // 13
你有它 - 只fibonacci (7)
使用匿名函数递归计算