Print the first n numbers of the fibonacci sequence in one expression

Question

So I've been messing around with Python a bit lately and I'm trying to find a way to output the nth number of the fibonacci sequence in a single expression. This is the code that I've written so far:

(lambda f: f if f<2 else (f-1)+(f-2))(n)
# n == 1 -> 1
# n == 2 -> 1
# n == 3 -> 3
# n == 4 -> 5
# n == 5 -> 7
....

However, as I commented above this simply outputs a set of odd numbers. I'm confused as to why this is happening because if I am to re-write this as a named lambda function, it would look something like this:

f = lambda n: n if n<2 else f(f-1)+f(f-2)
# f(1) -> 1
# f(2) -> 1
# f(3) -> 2
# f(4) -> 3
...
# f(10) -> 55
...

Now the reason I've added the Lambda Calculus tag is because I'm not sure if this question falls under the domain of simply understanding how Python handles this. I've read a tiny bit about the Y combinator in lambda calculus, but that's a foreign language to me and couldn't derive anything from resources I found for this about lambda calculus.

Now, the reason I'm trying to do this in one line of code, as opposed to naming it, is because I want to try and put this lambda function into list comprehension. So do something like this:

[(lambda f: f if f<2 else (f-1)+(f-2))(n) for n in range(10)]

and create an array of the first x numbers in the fibonacci sequence.

What I'm looking for is a method of doing this whole thing in one expression, and should this fall under the domain of Lambda calculus, which I believe it does, for someone to explain how this would work.

Feel free to offer an answer in JavaScript, C#, or other C-like languages that support Lambda functions.

EDIT: I've found the solution to what I was attempting to do:

[(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f:(lambda n: n if n<2 else f(n-1)+f(n-2)))(y) for y in range(10)]

I know that this is not at all practical and this method should never be used, but I was concerned with CAN I do this as opposed to SHOULD I ever do this.

Answer 1

You'll need to assign your lambda to an actual variable, and then call the lambda inside the lambda:

>>> g = lambda f: f if f < 2 else g(f-1)+g(f-2)
>>> [g(n) for n in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Answer 2

I have a one-line solution that meets your criteria, but it is one of the most crazy codes I ever written. It doesn't use list comprehension, but it mixes dynamic solution and lambda function in one line.

fib = (lambda n: (lambda fib: fib(fib, [], n, None))(lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))))

Just to explain it a bit. The first part (lambda fib: fib(fib, [], n, None)) take a lambda function as parameter and then call it with the parameters it expect. This trick allows us to assign a name to the lambda function and to pass this name to itself.. this is the magic.

Instead second part, the core function, lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))) uses another trick to implement the dynamic solution. The first parameter fib is a reference to itself, the second parameter, arr, is the array containing our solution and it is filled from left to right calling recursively fib exactly n times. The recursion ends when the third parameter i becomes 0. The fourth parameter is an ugly trick: it is not used by the function, but it is used to call the append method of arr.

This is absolutely the less elegant solution, but it is also the fastest one. I report the timings for N=500 below.

The naive solution is unfeasible, but here you can find the code to compute one element at a time of the series (this is probably what you wanted to mix lambda function and recursion):

(lambda n: ((lambda fib: fib(fib,n+1))(lambda fib, i: (1 if i <= 2 else fib(fib,i-2) + fib(fib,i-1)))))(N)

Solution proposed by @cdlane:

%timeit [0, 1] + [(4<<n*(3+n)) // ((4<<2*n)-(2<<n)-1) & ((2<<n)-1) for n in range(N)][1:]
10 loops, best of 3: 88.3 ms per loop

Solution proposed by @lehiester:

%timeit [int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x))) for x in range(N)]
1000 loops, best of 3: 1.49 ms per loop

My ugly solution:

%timeit (lambda n: (lambda fib: fib(fib, [], n, None))(lambda fib, arr, i, _: arr if i == 0 else fib(fib, arr, i-1, arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2]))))(N)
1000 loops, best of 3: 434 us per loop

Another ugly and faster solution which doesn't use the recursion:

%timeit (lambda n: (lambda arr, fib_supp: [arr] +  [fib_supp(arr) for i in xrange(n)])([], (lambda arr: arr.append(1) if len(arr) < 2 else arr.append(arr[-1]+arr[-2])))[0])(N)
1000 loops, best of 3: 346 us per loop

UPDATE

Finally I found an elegant way to formulate the one-line function. The idea is always the same, but using the setitem method instead of the append. Some of the trick I used can be found at this link. This approach is just a bit slower, but at least is readable:

%timeit (lambda n: (lambda arr, fib_supp: any(fib_supp(i, arr) for i in xrange(2,n)) or arr)([1] * n, (lambda i, arr: arr.__setitem__(i,(arr[i-1]+arr[i-2])))))(N)
1000 loops, best of 3: 385 us per loop

Answer 3

How about:

(lambda f: (4 << f * (3 + f)) // ((4 << 2 * f) - (2 << f) - 1) & ((2 << f) - 1))(n)

It doesn't start the sequence in the usual way:

0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, ...

But once you get past 1, you're fine. You'll find a detailed explanation in the blog entry An integer formula for Fibonacci numbers along with lots of related information.

On my system, @lehiester's golden ratio based solution goes off the rails at F71, producing 308061521170130, instead of 308061521170129 and continues to deviate from there.

Answer 4

lambda calculus via Python

Since this is tagged with lambda-calculus, rather than write an answer that relies on clever tricks or language features that are specific to python, I'm only going to use simple lambdas

U = lambda f: f (f)

Y = U (lambda h: lambda f: f (lambda x: h (h) (f) (x)))

loop = Y (lambda recur: lambda acc: lambda a: lambda b: lambda n:
  acc if n == 0 else
    recur (acc + [a]) (a + b) (a) (n - 1))

fibonacci = loop ([]) (0) (1)

print (fibonacci (10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Of course we used four named lambdas U, Y, loop, and fibonacci – because each lambda is a pure function, we can replace any reference to its name with its value

# in Y, replace U with its definition
Y = (lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x)))

# in loop, replace Y with its definition
loop = (lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
  acc if n == 0 else
    recur (acc + [a]) (a + b) (a) (n - 1))

# in fibonacci, replace loop with its definition
fibonacci = (lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
  acc if n == 0 else
    recur (acc + [a]) (a + b) (a) (n - 1)) ([]) (0) (1)

fibonacci is now a single, pure expression – we could call the lambda directly in the print statement...

# in print, replace fibonacci with its definition
print ((lambda f: f (f)) (lambda h: lambda f: f (lambda x: h (h) (f) (x))) (lambda recur: lambda acc: lambda a: lambda b: lambda n:
  acc if n == 0 else
    recur (acc + [a]) (a + b) (a) (n - 1)) ([]) (0) (1) (10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

---

once again, using another program

I wrote a very similar answer (also in Python) but in the context of a different program – it might be useful to help see the generality of the techniques

---

once again, in another language

We'll do the entire thing again only this time in JavaScript. JS is better suited for the demonstration this exercise because we can show the code working here in the browser and the lambda syntax is much more permissive (in terms of code formatting) – other than that, you'll notice the programs are almost identical

const U = f =>
  f (f)

const Y =
  U (h => f => f (x => h (h) (f) (x)))

const loop = Y (recur => acc => a => b => n =>
  n === 0
    ? acc
    : recur (acc.concat ([a])) (a + b) (a) (n - 1))

const fibonacci =
  loop ([]) (0) (1)

console.log (fibonacci (10))
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

// in Y, replace U with its definition
Y = (f => f (f)) (h => f => f (x => h (h) (f) (x)))

// in loop, replace Y with its definition
loop = (f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
  n === 0
    ? acc
    : recur (acc.concat ([a])) (a + b) (a) (n - 1))

// in fibonacci, replace loop with its definition
fibonacci = (f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
  n === 0
    ? acc
    : recur (acc.concat ([a])) (a + b) (a) (n - 1)) ([]) (0) (1)

fibonacci is now a single, pure expression – we could call the lambda directly in the console.log statement...

oh and it's really fast, too

console.time ('fibonacci (500)')
console.log ((f => f (f)) (h => f => f (x => h (h) (f) (x))) (recur => acc => a => b => n =>
  n === 0
    ? acc
    : recur (acc.concat ([a])) (a + b) (a) (n - 1)) ([]) (0) (1) (500))
console.timeEnd ('fibonacci (500)')
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 490 more items ]
// fibonacci (500): 3 ms

---

practice makes perfect

The lambda calculus has been one of my favourite areas of study. With just the Y-combinator alone, I've spent countless hours exploring its beauty and sophistication. I hope you find these explorations helpful. If you have any other questions on the subject matter, don't be shy to ask ^_^

Answer 5

You have to somehow assign a name to it in order to use a recursive definition--otherwise a recursive lambda function is impossible in Python since it doesn't have any special reflexive keyword that refers to it.

As @TerryA mentioned, you could use the trick in this post in order to generate a sequence of x Fibonacci numbers in one statement with the recursive definition.

Or, you could use the closed form, which would be much faster:

[int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x)))
 for x in range(10)]

This assumes that x is not very large, though, because the float arithmetic will overflow around x=600 and will probably have large rounding errors before that point--as @cdlane points out, this starts diverging from the actual sequence at x=71, i.e. x in range(72).

---

EDIT: @cdlane shared a closed form with only integer arithmetic, which should work for any x in theory. I would probably use this one instead of the expression above.

[0, 1] + [(4<<n*(3+n)) // ((4<<2*n)-(2<<n)-1) & ((2<<n)-1)
          for n in range(10)][1:]