斐波纳契上的U combinator：你如何将这段代码翻译成python？

我想了解combinators，我无法理解（Y overriding self-application）给出的示例。我认为我已经开始掌握这个概念，但我还很不理解。斐波纳契上的U combinator：你如何将这段代码翻译成python？

我想翻译下面的代码到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中编写给定示例的“文字”翻译？我怎么能这样做？

来源

2010-06-22 JPCosta

我写了一个简单的翻译，这似乎产生正确的结果：

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

好运理解combinators :)

来源

2010-06-22 21:29:28 Karmastan

是的，你是完全正确的！我认为这与（（f f）x）有关，但我不确定是什么。我改变了一点我的代码f（f）（x），它的工作。我花了大约1分钟来从python解释器计算U（fibnr）（35）。 – JPCosta 2010-06-22 22:07:55

斐波纳契上的U combinator：你如何将这段代码翻译成python？

回答

相关问题