python下lambda+尾递归

x2

原帖由 efhilt 于 2009-4-16 10:11 发表
其实一点都不难理解。这种写法纯属没事找事。

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

然后直接print A(A, 2)

Scheme版是这样的：

1. 
   
2. (define (F f)
   
3.   (lambda (n)
   
4.     (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

原帖由 x2 于 2009-4-16 19:29 发表


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数。

1. 
   
2. (define (Y f)
   
3.   ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))
   

复制代码

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

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

xiaoyu9805119

学习了，感谢分享

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

izhier

原帖由 x2 于 2009-4-16 19:29 发表
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 版是这样的

1. 
   
2. f = \n -> if n == 1 then 1 else n * f(n-1)
   
3. 
   
4. 或
   
5. 
   
6. f 1 = 1
   
7. f (n+1) = (n+1) * f  n
   

复制代码

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

x2

原帖由 izhier 于 2009-4-17 09:10 发表

Haskell 版是这样的

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

或

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

1. 
   
2. fix :: (a -> a) -> a
   
3. fix f = f (fix f)
   
4. 
   
5. fact f 0 = 1
   
6. fact f x = x * f (x-1)
   

复制代码

1. 
   
2. (fix fact) 5
   
3. 120
   

复制代码

x2

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

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

复制代码

再输入:

1. 
   
2. ((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

看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

1. 
   
2. guile> (define (fix f) (lambda (x) ((f (fix f)) x)))
   
3. guile> (define (fact f) (lambda (n) (if (= n 1) 1 (* n (f (- n 1))))))
   
4. guile> ((fix fact) 10)
   
5. 3628800
   

复制代码

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

mhsy2003

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

x2

原帖由 mhsy2003 于 2009-4-17 13:02 发表
呵呵，请问我那个python的版本也能算strict version 的Y Combinator不？ 如果不是我就理解不对了...

而且还是尾递归的。

victorlee129

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