# Making this reduce() Fibonacci generator better

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

• Why do you want to use reduce? Commented Jan 28, 2013 at 16:14
• Because it seemed cool. I want to use something like reduce, or map. Because it seems like a challenge. Commented Jan 28, 2013 at 16:18
• @CrisStringfellow It's not really the right tool for the job. A generator would be the best choice. Commented Jan 28, 2013 at 23:06
• @Lattyware okay but a generator is just too easy. Commented Jan 29, 2013 at 7:39

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

• That is awesome. Commented Jan 29, 2013 at 7:46

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

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

• 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 Commented Jan 28, 2013 at 21:41
• Yes: that's why I described it as "cool rather than useful"! Commented Jan 28, 2013 at 21:45
• I like that a lot the second snippet. Commented Jan 29, 2013 at 7:41

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