U Combinator على فيبوناتشي: كيف يمكنك ترجمة هذا الرمز إلى بيثون؟

Question

أحاول أن أتعرف على المدمجون وأواجه مشكلة في فهم المثال المقدم على (y التغلب على التطبيق الذاتي). أعتقد أنني بدأت في فهم المفهوم ولكني ما زلت بعيدًا عن الفهم.

أرغب في ترجمة الكود التالي إلى بيثون:

     (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>

لذلك ، هل من الممكن كتابة ترجمة "حرفية" للمثال المعطى في بيثون؟ كيف يمكنني فعل ذلك؟

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

أو إذا كنت تحب Lambdas حقًا:

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

أعتقد أن مشكلتك الأولية كانت ترجمة Lisp ((f f) x) في بيثون f(f(x)) بدلاً من f(f)(x).

حظا سعيدا فهم المدمجات :)