# 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? – Winston Ewert Jan 28 '13 at 16:14
Because it seemed cool. I want to use something like reduce, or map. Because it seems like a challenge. – Cris Stringfellow Jan 28 '13 at 16:18
@CrisStringfellow It's not really the right tool for the job. A generator would be the best choice. – Latty Jan 28 '13 at 23:06
@Lattyware okay but a generator is just too easy. – Cris Stringfellow Jan 29 '13 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. – Cris Stringfellow Jan 29 '13 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
from operator import add

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 – tokland Jan 28 '13 at 21:41
Yes: that's why I described it as "cool rather than useful"! – Gareth Rees Jan 28 '13 at 21:45
I like that a lot the second snippet. – Cris Stringfellow Jan 29 '13 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'.

-
Thanks! I really appreciate all the info. – Cris Stringfellow Jan 29 '13 at 17:06