1

Y 组合子（来自维基百科文章）定义为：

Y = \f.(\x.f(x x)) (\x.f(x x))

所以当我们在 g 上调用 Y 时：

Y g = (\f.(\x.f(x x)) (\x.f(x x))) g 

= (\x.g(x x)) (\x.g(x x))

= g((\x.g(x x)) (\x.g(x x)))

= g (Y g)

重复导致：

Y g = g(Y g) = g(g(Y g)) = g(...g(Y g)...)

因为这个展开是在一元函数之上的，所以我不知道这是左折叠还是右折叠。

我对左折叠的理解是它类似于这个（使用二元函数 f）：

f (f (f (f 1 2) 3) 4) 5)

而二进制函数 f 的右折叠如下所示：

f 1 (f 2 (f 3 (f 4 5)))

但是，我想任何一元函数看起来都与左折叠或右折叠扩展相同：

f (f (f (f (f x))))

这个对吗？如果不是，Y 组合器是展开成左折叠还是右折叠？

4

1 回答 1

4

定点组合器Y仅启用匿名递归。你用这个递归做什么完全取决于你。您可以使用它定义左关联折叠和右关联折叠。我希望你不介意我用 Javascript 说明这一点：

// simplified Y combinator with eta abstraction due to eager evaluation

const fix = f => x => f(fix(f)) (x);

// left fold

const foldl = fix(rec => f => acc => ([x, ...xs]) =>
  x === undefined
    ? acc
    : rec(f) (f(acc) (x)) (xs));
    
// right fold

const foldr = fix(rec => f => acc => ([x, ...xs]) =>
  x === undefined
    ? acc
    : f(x) (rec(f) (acc) (xs)));
    
    
 console.log(
   foldl(x => y => x - y) (0) ([1,2,3])); // -6
   
  console.log(
   foldr(x => y => x - y) (0) ([1,2,3])); // 2

于 2020-01-17T12:49:31.353 回答