Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

share|improve this question
2  
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. –  Lattyware Jan 28 '13 at 23:06
    
@Lattyware okay but a generator is just too easy. –  Cris Stringfellow Jan 29 '13 at 7:39
add comment

3 Answers 3

up vote 4 down vote accepted

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
share|improve this answer
    
That is awesome. –  Cris Stringfellow Jan 29 '13 at 7:46
add comment

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))
share|improve this answer
2  
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
add comment

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

share|improve this answer
    
Thanks! I really appreciate all the info. –  Cris Stringfellow Jan 29 '13 at 17:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.