Y Combinator学习总结

Tue, Jan 26, 2021

Y Combinator学习总结

scheme版本Y组合子

(define Y
  (lambda (le) 
    ((lambda (f) (f f)) 
      (lambda (f) 
        (le (lambda (x) ((f f) x)))))))

直接翻译为erlang代码

Y = fun(M) -> 
  (fun(F) -> F(F) end)(
    fun(F) ->
      M(fun(X) -> (F(F))(X) end) 
    end
  ) 
end.

这样看起来不怎么清晰，抽取函数体，定义为变量，再带入fun(F) -> F(F) end即获得

Y = fun(M) -> 
  G = fun (F) -> M(fun(X) -> (F(F))(X) end) end,
  G(G)
end.

Y组合子是用于lambda演算中实现递归逻辑的，即是可以实现匿名函数的递归调用。原理就是fixed-point combinator，不动点组合子。高阶函数f的不动点是另一个函数 g，使得f(g) = g。那么不动点算子是任何函数fix使得对于任何函数f都有f(fix(f)) = fix(f)。这样就可以实现匿名函数把自己算出来，从而间接调用会自己，实现递归了。

Fac = fun (F) ->
  fun (0) -> 1;
    (N) -> N * F(N-1)
  end
end.

(Y(Fac))(5). % 120

BTW, Erlang R17以后支持Named Function [1]和[2]，现在递归可以写成

Fun = fun Fact(N) when N > 0 ->
      N * Fact(N - 1);
    Fact(0) ->
      1
end.

Fun(5). % 120

参考：