>>> 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 ...
>>> 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))
120
将2楼的程序抽象了一下。
(define (F g) (lambda ( . x) (apply g (cons g x))))
(define fact (lambda (s c n v) (if (= c n) v (s s (1+ c) n (* (1+ c) v)))))
((F fact) 1 5 1)
2楼的Y Combinator看起来长得不像Y Combinator, Y Combinator看起来应该似一个不动点函数，而2楼的看上去不似。
[ 本帖最后由 x2 于 2009-4-17 14:56 编辑 ]
回复 #21 x2 的帖子
恩晚上在隧道里走路的时候我也意识到这个问题，我写的那个不能算Y-Combinator，只是结果像。lambda的参数还是个lambda，并且后者长的跟前者像，呵呵，直接用self替代下后者才是。。。
所以那个严格上来说也不能算递归，因为两个lambda并不是一个实体，也就是说没有达到自己调用自己。。。
:mrgreen:
我写错了~~~
这个很bug...
[ 本帖最后由 mhsy2003 于 2009-4-18 00:09 编辑 ]
回复 #20 victorlee129 的帖子
你这个才是我想写的，呵呵，thanks 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
试一试((lambda (x) (x x) (lambda (x) (x x))
和(lambda x : x(x)) (lambda x : x(x))
[ 本帖最后由 x2 于 2009-4-18 21:51 编辑 ]
回复 #24 x2 的帖子
我没看懂FIX的实现。我晕了。
:emn58: FIX有懒惰与勤劳之分：
先看懒惰的FIX, 懒惰的FIX比较容易理解, 可惜Python不能用这个懒惰的FIX:
FIX = lambda f : (lambda x : f (x (x))) (lambda x : f (x (x)))
假设存在阶乘函数FACT,
FACT= lambda f : lambda v : lambda c : value if count == 0 else f(v*c)(c-1)
将懒惰的FIX作用与FACT,得到：
(lambda x : FACT (x (x))) (lambda x : FACT (x (x)))
FACT ((lambda x : FACT (x x)) (lambda x : FACT (x x)))
FACT 后的括号中的表达式就是FIX(FACT)的定义，于是得到：
FIX (FACT)(v)(c) = FACT (FIX(FACT))(v)(c)
FIX (FACT)(v)(c) = lambda v : lambda c : value if count == 0 else FIX(FACT)(v*c)(c-1) FIX(FACT)缩写为fact
fact(v)(c) = value if count == 0 else fact(v*c)(c-1)
这和http://blog.csdn.net/pongba/archive/2006/10/15/1336028.aspx上讲的是一回事。
let power_gen = lambda self. P(self(self))
let Y = lambda F.
let f_gen = lambda self. F(self(self))
return f_gen(f_gen)
参考http://zh.wikipedia.org/wiki/不动点组合子 勤奋的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 编辑 ]