U комбинатор по Фибоначчи: как бы вы перевели этот код на Python? - PullRequest
Новая
       31

U комбинатор по Фибоначчи: как бы вы перевели этот код на Python?

2 голосов
/ 23 июня 2010

Я пытаюсь узнать о комбинаторах, и у меня возникают проблемы с пониманием примера, приведенного в ( 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)))

Но это не работает (я думаю, что это связано с порядком, в котором функции оцениваются внутри лямбды).

Поэтому я попытался использовать композицию функций как: 

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

Но все равно не сработало, когда я вызываю мой последний фрагмент кода, я получаю лямбду: 

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

Итак, возможно ли написать «буквальный» перевод данного примера на Python? Как я мог это сделать?

1 Ответ

3 голосов
/ 23 июня 2010

Я написал простой перевод, который, кажется, дает правильные результаты: 

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

Или, если вам действительно нравятся лямбды: 

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

Удачи в понимании комбинаторов:)

...