[Erlang 0056] 用fun在Erlang Shell中编写尾递归 Ⅱ

pennate

　　 之前研究了一个问题"[Erlang 0050]用fun在Erlang Shell中编写尾递归",一直对这个问题保持着关注;最近在搜索引擎里找到同一个问题,题目足够清晰calling fun() from fun() 它提供了另外一种解决解决方案:Y-combinator!





%%That's easy, you need the Y-combinator!

y(M) ->
G = fun (F) -> M(fun(A) -> (F(F))(A) end) end,
G(G).
and then you define you fun with a fun wrapper like so:
Fac -> fun (F) ->
fun (0) -> 1;
(N) -> N * F(N-1)
end
end.
and call it like:
(y(Fac))(5)
120

　　不错吧,不过我们的目标是在shell里面直接实现尾递归,所以要动手简单改造一下





Eshell V5.9  (abort with ^G)
1> Y=fun(F) ->
1>     G = fun(T) ->
1>         F(fun(X) -> (T(T))(X) end)
1>     end,
1>     G(G) end.
#Fun
2>  
2> Fac = fun (F) ->
2>           fun (0) -> 1;
2>               (N) -> N * F(N-1)
2>           end
2>       end.
#Fun
3>
3> (Y(Fac))(5).
120
4> Fib = fun(F) ->
4>           fun(0) -> 0;
4>              (1) -> 1;
4>              (N) -> F(N-1) + F(N-2)
4>           end
4>       end.
#Fun
5>
5> (Y(Fib))(8).
21
6>
　　问题还没有结束,对于两个参数的怎么办呢?Y函数比较直观,可以修改为:




6> Y2=fun(F) ->
6>     G = fun(T) ->
6>         F(fun(Y, Z) -> (T(T))(Y, Z) end)
6>     end,
6>     G(G) end.
#Fun
7>  Func2=fun(F)->
7>           fun(X,Y) when Yio:format("~p,",[X+Y]), F(Y,X+Y);  
7>           (X,Y) -> done   
7>                end
7>        end.
#Fun
8>
8> (Y2(Func2))(0,1).
1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,done
　　  当然多个参数我们可以使用apply mfa的方式来处理多个参数的情况.同时Y方法也可以放在user_default里面方便后续使用.实践之后说一点理论吧,这种解决方案是使用了Y combinator可能最近你已经频繁接触到这个名字,比如在IT新闻,比如在,它本身是一个数学概念,那么我们从维基百科开始:


　　英文维基
　　Fixed-point combinator http://en.wikipedia.org/wiki/Fixed-point_combinator
　　Y combinator: http://rosettacode.org/wiki/Y_combinator
　　中文维基
　　不动点组合子 http://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8A%A8%E7%82%B9%E7%BB%84%E5%90%88%E5%AD%90
　　不动点 http://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8A%A8%E7%82%B9
　　λ演算 http://zh.wikipedia.org/wiki/%E6%97%A0%E7%B1%BB%E5%9E%8B_lambda_%E6%BC%94%E7%AE%97


　　
　　 我们理顺一下里面的逻辑关系,从不动点开始:
　　 在数学中，函数的不动点或定点是指被这个函数映射到其自身一个点.例如,定义在实数上的函数f,f(x)=x2-3x+4则2是函数f的一个不动点，因为f(2)=2.也不是每一个函数都具有不动点。例如定义在实数上的函数,f(x)=x+1就没有不动点。因为对于任意的实数，x永远不会等于x+1。用画图的话来说，不动点意味着点(x,f(x))在直线y=x上，或者换句话说，函数f的图像与那根直线有共点。上例f(x)=x+1的情况是，这个函数的图像与那根直线是一对平行线.


　　 我用wolframalpha.com绘制了f(x)=x2-3x+4的函数图:


　　   接下来我们看不动点组合子(Fixed-point combinator,或不动点算子)是计算其他函数的一个不动点的高阶函数.函数 f 的不动点是一个值 x 使得 f(x) = x.例如,0 和 1 是函数 f(x) = x2 的不动点,因为 02 = 0 而 12 = 1.鉴于一阶函数(在简单值比如整数上的函数)的不动点是个一阶值,高阶函数 f 的不动点是另一个函数 g 使得 f(g) = g.那么,不动点算子是任何函数 fix 使得对于任何函数 f 都有f(fix(f)) = fix(f).不动点组合子允许定义匿名的递归函数.
　　   然后接下来是Y combinator(Y组合子)在无类型 lambda 演算中众所周知的(可能是最简单的)不动点组合子叫做 Y 组合子.它是 Haskell B. Curry 发现的,定义为

Y = λf.(λx.f (x x)) (λx.f (x x))  %%用一个例子函数g来展开它，我们可以看到上面这个函数是怎么成为一个不动点组合子的Y g = (λf.(λx . f (x x)) (λx . f (x x))) gY g = (λx. g (x x)) (λx . g (x x))          %%λf 的 β-归约 - 应用主函数于 gY g = (λy. g (y y)) (λx . g (x x))          %%α-转换 - 重命名约束变量Y g = g ((λx. g (x x)) (λx . g (x x)))     %%λy 的 β-归约 - 应用左侧函数于右侧函数Y g = g (Y g)   %%Y 的定义 　　  这个!?在编程语言里面怎么实现呢?看一下http://rosettacode.org/wiki/Y_combinator 这里罗列了大多数语言对Y combinator的实现,比如C#版本:

　　delegate Func Recursive(Recursive recursive);
void Main()
{
        Func, Func< int, int>> Y =
            f => ((Recursive)(g => (f(x => g(g)(x)))))((Recursive)(g => f(x => g(g)(x))));

　　        var fac = Y(f => x => x < 2 ? 1 : x * f(x - 1));
        var fib = Y(f => x => x < 2 ? x : f(x - 1) + f(x - 2));
　　
        Console.WriteLine(fac(6));
        Console.WriteLine(fib(6));
}

　　  不过注意一下Erlang版本的实现,上面提供了另外一种实现方式(只不过在下面这种实现中,怎么使用多个参数呢?):



Eshell V5.9  (abort with ^G)
1> Y = fun(M) -> (fun(X) -> X(X) end)(fun (F) -> M(fun(A) -> (F(F))(A) end) end) end.
#Fun
2> Fac = fun (F) ->
2>           fun (0) -> 1;
2>               (N) -> N * F(N-1)
2>           end
2>       end.
#Fun
3> (Y(Fac))(5).      
120
4>
4> Fib = fun(F) ->
4>           fun(0) -> 0;
4>              (1) -> 1;
4>              (N) -> F(N-1) + F(N-2)
4>           end
4>       end.
#Fun
5> (Y(Fib))(8).     

　　
  沿着Y Combinator这个线索,可以找到更多的资料,
[PDF]  The Why of Y - Dreamsongs  
　　[1] Y Combinator in Erlang
　　[2] Deriving the Y Combinator in Erlang  (原文已经被墙,这是我拷贝出来的副本)