Making this reduce() Fibonacci generator better

Question

I've recently discovered how cool reduce() could be and I want to do this:

>>> a = [1, 1] + [0] * 11
>>> count = 1
>>> def fib(x,n):
...     global count
...     r = x + n
...     if count < len(a) - 1: a[count+1] = r
...     count += 1
...     return r
>>>
>>> reduce(fib,a,1)
610
>>> a
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]

But this just looks so messy and almost defeats the purpose of the last line:

reduce(fib,a,1)

What would be a better way to use Python to make a Fibonacci number with reduce()?

Answer 1

A reduce (that's it, a fold) is not exactly the abstraction for the task (what input collection are you going to fold here?). Anyway, you can cheat a little bit and fold the indexes even if you don't really use them within the folding function. This works for Python 2.x:

def next_fib((x, y), n):
    return (y, x + y)

reduce(next_fib, xrange(5), (1, 1))[0]
#=> 8

Answer 2

If you set

def fib(x, _):
    x.append(sum(x[-2:]))
    return x

then:

>>> reduce(fib, xrange(10), [1, 1])
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

But as long as you're looking for something cool rather than something useful, how about this? In Python 3.3:

from itertools import islice
from operator import add

def fib():
    yield 1
    yield 1
    yield from map(add, fib(), islice(fib(), 1, None))

Answer 3

In your case, the interesting part of reduce is to re-apply a function. So, let's define :

>>> def ncompose(f, a, n): return a if n <= 0 else ncompose(f, f(a), n-1)

Then,

>>> def fibo((a,b)): return (b, a+b)
>>> ncompose(fibo, (1,1), 5)[0]
8

Since you like to play with reduce, let's use it to perform composition :

>>> reduce(lambda a,f: f(a), [fibo]*5, (1,1))

Like @tokland's answer, it's quite artificial (building n items only as a way to iterate n times).

A side note : Haskell and Scala should provide you even more fun'.