python下lambda+尾递归

x2

原帖由 mhsy2003 于 2009-4-16 09:03 发表
>>> print ((lambda self,n:1 if n==1 else n*self(self,n-1))((lambda self,n:1 if n==1 else n*self(self,n-1)),2))
2
>>> print ((lambda self,count,n,value:value if count==n else self(self,count+1,n ...

1. 
   
2. >>> print ((lambda self,count,n,value:value if count==n else self(self,count+1,n,(count+1)*value))((lambda self,count,n,value:value if count==n else self(self,count+1,n,(count+1)*value)),1,5,1))
   
3. 120
   

复制代码

将2楼的程序抽象了一下。

1. 
   
2. (define (F g) (lambda ( . x) (apply g (cons g x))))
   
3. 
   
4. (define fact (lambda (s c n v) (if (= c n) v (s s (1+ c) n (* (1+ c) v)))))
   
5. 
   
6. ((F fact) 1 5 1)
   

复制代码

2楼的Y Combinator看起来长得不像Y Combinator, Y Combinator看起来应该似一个不动点函数，而2楼的看上去不似。

[ 本帖最后由 x2 于 2009-4-17 14:56 编辑 ]

mhsy2003

恩  晚上在隧道里走路的时候我也意识到这个问题，我写的那个不能算Y-Combinator，只是结果像。
lambda的参数还是个lambda，并且后者长的跟前者像，呵呵，直接用self替代下后者才是。。。
所以那个严格上来说也不能算递归，因为两个lambda并不是一个实体，也就是说没有达到自己调用自己。。。


我写错了~~~
这个很bug...

[ 本帖最后由 mhsy2003 于 2009-4-18 00:09 编辑 ]

mhsy2003

你这个才是我想写的，呵呵，thanks

x2

FIX是一个不动点组合子，将FIX作用在函数f上会返回f本身 fix f = f(fix f)，这是实现递归的关键。

>>> FIX=lambda f : (lambda x : f(lambda *y : x(x)(*y))) (lambda x : f(lambda *y : x(x)(*y))) >>> FIX (lambda f : lambda value : lambda count : value if count == 0 else f((value*count))(count-1))(1)(100) 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

试一试

1. ((lambda (x) (x x) (lambda (x) (x x))

复制代码

和

1. (lambda x : x(x)) (lambda x : x(x))

复制代码

[ 本帖最后由 x2 于 2009-4-18 21:51 编辑 ]

mhsy2003

我没看懂FIX的实现。
我晕了。

x2

FIX有懒惰与勤劳之分：
先看懒惰的FIX, 懒惰的FIX比较容易理解, 可惜Python不能用这个懒惰的FIX:

1. 
   
2. FIX = lambda f : (lambda x : f (x (x))) (lambda x : f (x (x)))
   

复制代码

假设存在阶乘函数FACT,

1. 
   
2. FACT  = lambda f : lambda v : lambda c : value if count == 0 else f(v*c)(c-1)
   

复制代码

将懒惰的FIX作用与FACT,得到：

1. 
   
2. (lambda x : FACT (x (x))) (lambda x : FACT (x (x)))
   
3. FACT ((lambda x : FACT (x x)) (lambda x : FACT (x x)))
   

复制代码

FACT 后的括号中的表达式就是FIX(FACT)的定义，于是得到：

1. 
   
2. FIX (FACT)(v)(c) = FACT (FIX(FACT))(v)(c)
   
3. FIX (FACT)(v)(c) = lambda v : lambda c : value if count == 0 else FIX(FACT)(v*c)(c-1) FIX(FACT)缩写为fact
   
4. fact(v)(c)       = value if count == 0 else fact(v*c)(c-1)
   

复制代码

这和http://blog.csdn.net/pongba/archive/2006/10/15/1336028.aspx上讲的是一回事。

1. 
   
2. let power_gen = lambda self. P(self(self))
   
3. let Y = lambda F.
   
4.          let f_gen = lambda self. F(self(self))
   
5. return f_gen(f_gen)
   

复制代码

参考http://zh.wikipedia.org/wiki/不动点组合子

x2

勤奋的FIX和懒惰的FIX类似：

fix=lambda f : (lambda x : lambda *y : f (x (x)) (*y))                (lambda x : lambda *y : f (x (x)) (*y)) fix(g) (a)(b) = (lambda x : lambda *y : g (x (x)) (*y))                 (lambda x : lambda *y : g (x (x)) (*y))(a)(b)               = (lambda *y : g ((lambda x : lambda *y : g (x (x)) (*y))                                 (lambda x : lambda *y : g (x (x)) (*y))) (*y))(a)(b)               = g ((lambda x : lambda *y : g (x (x)) (*y))                    (lambda x : lambda *y : g (x (x)) (*y))) (a)(b)               = g (fix (g)) (a)(b)

[ 本帖最后由 x2 于 2009-4-19 18:26 编辑 ]