Y Combinator是左折还是右折？

Question

Y 组合器（来自 wikipedia article）定义为：

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组合子是展开成左折还是右折？

Answer 1

像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

Y Combinator是左折还是右折？

Is the Y Combinator a left fold or a right fold?

recursion

functional-programming

fold

lambda-calculus

y-combinator