在斐波那契上使用U组合子：如何将此代码翻译为Python？

Question

我正在学习组合子（combinators），但对一个例子感到有些困惑，那个例子可以在这个链接找到（Y 重写自应用）。我觉得我开始理解这个概念了，但距离完全明白还有很大差距。

我想把以下代码翻译成Python：

     (define (U f) (f f))

     (define (fib-nr f)
       (lambda (n)
         (if (< n 2) 1 (+ ((f f) (- n 1)) ((f f) (- n 2))))))

     # Usage:   
     ((U fib-nr) 35) ;==> 14930352

我尝试了一个“字面”的翻译，写成了：

U = lambda u: u(u)

def fibnr(f):
    return lambda n:  1 if (n<2) else (f (f (n-1))) + (f (f (n-2)))

但这并不奏效（我觉得这和lambda内部函数的评估顺序有关）。

于是我尝试使用函数组合，写成：

# http://code.activestate.com/recipes/52902-function-composition/
class compose:
    '''compose functions. compose(f,g,x...)(y...) = f(g(y...),x...))'''
    def __init__(self, f, g, *args, **kwargs):
        self.f = f
        self.g = g
        self.pending = args[:]
        self.kwargs = kwargs.copy()

    def __call__(self, *args, **kwargs):
        return self.f(self.g(*args, **kwargs), *self.pending, **self.kwargs)


U = lambda u: compose(u, u)

def fibnr(f):
    ff = compose(f, f)
    return lambda n:  1 if (n<2) else (ff (n-1)) + (ff (n-2))

但还是不行，当我调用我最后那段代码时，得到的还是一个lambda。

>>> U(fibnr)(35)
<function <lambda> at 0x01A1B6B0>

那么，是否有可能把给定的例子“字面”翻译成Python呢？我该怎么做呢？

Answer 1

我写了一个简单的翻译，结果看起来是正确的：

def U(f): return f(f)

def fibnr(f):
    def lam(n):
        if (n < 2): return 1
        return f(f)(n-1) + f(f)(n-2)
    return lam

或者如果你真的喜欢用lambda表达式：

def fibnr(f): return lambda n: 1 if (n < 2) else f(f)(n-1) + f(f)(n-2)

我觉得你最开始的问题是把Lisp中的 ((f f) x) 翻译成了Python的 f(f(x))，而不是 f(f)(x)。

祝你好运理解组合子 :)