# Tutorial :U combinator on a fibonacci : how would you translate this code to python? ### Question:

I am trying to learn about combinators and I am having trouble understand the example given at (Y overriding self-application). I think I am beginning to grasp the concept but I am still far from understanding.

I would like to translate the following code to 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  ``

I tried a 'literal' translation by writing:

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

But this doesnt work (I think it has to do with the order the functions are evaluated inside the lambda).

So I tried to use function composition as:

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

But still didn't work, when calling my last snippet of code I get a lambda back:

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

So, is it possible to write a 'literal' translation of the given example in Python? How could I do it?

### Solution:1

I wrote a simple translation that seems to produce correct results:

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

Or if you really like lambdas:

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

I think your initial problem was translating Lisp `((f f) x)` into Python `f(f(x))` instead of `f(f)(x)`.

Good luck understanding combinators :)

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »