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

• Winston Ewert: Why do you want to use reduce?
• Cris Stringfellow: Because it seemed cool. I want to use something like reduce, or map. Because it seems like a challenge.
• Latty: @CrisStringfellow It's not really the right tool for the job. A generator would be the best choice.
• Cris Stringfellow: @Lattyware okay but a generator is just too easy.

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

• Cris Stringfellow: That is awesome.

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

• tokland: I guess the second snippet tries to mimic Haskell's fibs = 0 : 1 : zipWith (+) fibs (tail fibs). Unfortunately this is terribly inefficient in Python, you'd need to write it in more verbose manner using corecursion and itertools.tee (thus the beauty of the Haskell solution completely vanishes). en.wikipedia.org/wiki/Corecursion
• Gareth Rees: Yes: that's why I described it as "cool rather than useful"!
• Cris Stringfellow: I like that a lot the second snippet.

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