javascript - javascript 中的 y 组合器

Question

我在js中构建了一个像这样的y组合器

const y = f => { const g = self => x => f(self(self))(x); return g(g);}

我像这样简化了这段代码

 const y = f => { const g = self => f(self(self)); return g(g);}

这会得到无限递归。 这两个版本有什么区别？

Answer 1

如果您不理解两者之间的区别，我会很惊讶您实际上构建了它们。尽管如此，也许展示两者之间差异的最好方法是遵循他们的评估

const y = f => {
  const g = self => x => f(self(self))(x)
  return g(g)
}

y (z) ...
// (self => x => z(self(self))(x)) (self => x => z(self(self))(x)) ...
// returns:
// x => z((self => x1 => z(self(self))(x1))(self => x2 => z(self(self))(x2)))(x)

好的，所以 y(z) (其中 z 是某个函数，没关系)返回一个函数 x => ...。在我们应用该函数之前，评估将停止。

现在让我们将其与您的第二个定义进行比较

const y = f => {
  const g = self => f(self(self))
  return g(g)
}

y (z) ...
// (self => z(self(self))) (self => z(self(self)))
// z((self => z(self(self)))(self => z(self(self)))) ...
// z(z((self => z(self(self)))(self => z(self(self))))) ...
// z(z(z((self => z(self(self)))(self => z(self(self)))))) ...
// z(z(z(z((self => z(self(self)))(self => z(self(self))))))) ...
// ... and on and on

因此，y (z) 永远不会终止——至少在使用应用顺序求值的 JavaScript 中——其中函数参数在应用被调用函数之前先求值

<小时/>

替代 Y 组合器

在这里我们可以从头开始构建一个 Y 组合器

// standard definition
const Y = f => f (Y (f))

// prevent immediate infinite recursion in applicative order language (JS)
const Y = f => f (<b>x =></b> Y (f) <b>(x)</b>)

// remove reference to self using U combinator
const U = f => f (f)
const Y = <b>U (h =></b> f => f (x => <b>h (h)</b> (f) (x))<b>)</b>

让我们测试一下

const U = f => f (f)

const Y = U (h => f => f (x => h (h) (f) (x)))

// range :: Int -> Int -> [Int]
const range = Y (f => acc => x => y =>
  x > y ? acc : f ([...acc,x]) (x + 1) (y)) ([])

// fibonacci :: Int -> Int
const fibonacci = Y (f => a => b => x =>
  x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
  
console.log(range(0)(10).map(fibonacci))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

或者我最近最喜欢的

// simplified Y
const Y = f => x => f (Y (f)) (x)

// range :: Int -> Int -> [Int]
const range = Y (f => acc => x => y =>
  x > y ? acc : f ([...acc,x]) (x + 1) (y)) ([])

// fibonacci :: Int -> Int
const fibonacci = Y (f => a => b => x =>
  x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
  
console.log(range(0)(10).map(fibonacci))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]