论坛 › Python › python下lambda+尾递归

x2 发表于 2009-04-16 19:29

原帖由 efhilt 于 2009-4-16 10:11 发表 http://bbs3.chinaunix.net/images/common/back.gif
其实一点都不难理解。这种写法纯属没事找事。

A = lambda A, n : 1 if n == 1 else n * A(A, n -1)

然后直接print A(A, 2)

Scheme版是这样的：

(define (F f)
(lambda (n)
    (if ((zero? n) #t #f) one (mul n (f (sub-1 n))))))


Python版应该是这样的：
F=lambda f:lambda n: 1 if n == 1 else * f(n-1)

x2 发表于 2009-04-16 20:06

原帖由 x2 于 2009-4-16 19:29 发表 http://bbs3.chinaunix.net/images/common/back.gif


Scheme版是这样的：

(define (F f)
(lambda (n)
    (if ((zero? n) #t #f) one (mul n (f (sub-1 n))))))


Python版应该是这样的：
F=lambda f:lambda n: 1 if n == 1 else * f(n-1)

((Y F) three) 求3的阶乘，Y是Y Combinator, three是Church计数的3, 不必是Church数。

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


想演示Y Combinator要找一个采用惰性求值的求值器, 没的话要动手写一个。

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

xiaoyu9805119 发表于 2009-04-17 08:18

学习了，感谢分享

# 不建议实际环境如此写法

izhier 发表于 2009-04-17 09:10

原帖由 x2 于 2009-4-16 19:29 发表 http://bbs3.chinaunix.net/images/common/back.gif
Scheme版是这样的：

(define (F f)
(lambda (n)
    (if ((zero? n) #t #f) one (mul n (f (sub-1 n))))))

Python版应该是这样的：

F=lambda f:lambda n: 1 if n == 1 else * f(n-1)
Haskell 版是这样的:mrgreen:

f = \n -> if n == 1 then 1 else n * f(n-1)

或

f 1 = 1
f (n+1) = (n+1) * fn


[ 本帖最后由 izhier 于 2009-4-17 09:15 编辑 ]

x2 发表于 2009-04-17 11:21

原帖由 izhier 于 2009-4-17 09:10 发表 http://bbs3.chinaunix.net/images/common/back.gif

Haskell 版是这样的:mrgreen:

f = \n -> if n == 1 then 1 else n * f(n-1)

或

f 1 = 1
f (n+1) = (n+1) * fn


fix :: (a -> a) -> a
fix f = f (fix f)

fact f 0 = 1
fact f x = x * f (x-1)


(fix fact) 5
120

x2 发表于 2009-04-17 11:31

原来可以在一个采用了惰性求值的Scheme求值器中输入(必须采用惰性求值)：

(define (FIX f) (f (FIX f)))
(define (FACT f) (lambda (n) (if (= n 1) 1 (* n (f (- n 1))))))

再输入:

((FIX FACT) 10)

得到输出:3628800

原来http://blog.csdn.net/pongba/archive/2006/10/15/1336028.aspx讲的Y Combinator 其实就是这样一回事。
上面那个FIX就相当于一个Y Combinator。

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

x2 发表于 2009-04-17 12:02

看http://en.wikipedia.org/wiki/Fixed_point_combinator, 有一个strict version 的Y Combinator：
>>> fix = lambda f : lambda x : f(fix(f))(x)
>>> fact = lambda f : lambda n : 1 if n == 1 else n*f(n-1)
>>> fix(fact)(10)
3628800


guile> (define (fix f) (lambda (x) ((f (fix f)) x)))
guile> (define (fact f) (lambda (n) (if (= n 1) 1 (* n (f (- n 1))))))
guile> ((fix fact) 10)
3628800


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

mhsy2003 发表于 2009-04-17 13:02

回复 #17 x2 的帖子

呵呵，请问我那个python的版本也能算strict version 的Y Combinator不？:mrgreen: 如果不是我就理解不对了...

x2 发表于 2009-04-17 14:23

原帖由 mhsy2003 于 2009-4-17 13:02 发表 http://bbs3.chinaunix.net/images/common/back.gif
呵呵，请问我那个python的版本也能算strict version 的Y Combinator不？:mrgreen: 如果不是我就理解不对了...
而且还是尾递归的。

victorlee129 发表于 2009-04-17 14:50

可以直接：
reduce
或
lambda n:n==1 and 1 or n*self(n-1)

查看完整版本: python下lambda+尾递归