# Sequence generation problem - Fibonacci

Below is the representation and user interface fib_sequence for generating a Fibonacci sequence:

empty_rlist = None
#Representation - start
#Constructor
def rlist(first, rest):
return (first, rest)

#Selector
def first(s):
return s[0]

def rest(s):
return s[1]

#Representation - end

def fib_sequence(k):
prev, curr = 1, 0
def generate_sequence(prev, curr, k):
if k == 0:
return empty_rlist
elif k == 1:
return (curr, empty_rlist)
else:
return rlist(curr, generate_sequence(curr, prev+curr, k - 1))
return generate_sequence(prev, curr, k)


Program output:

>python -i fibonacci_sequence.py
>>> fib_sequence(0)
>>> fib_sequence(1)
(0, None)
>>> fib_sequence(2)
(0, (1, None))
>>> fib_sequence(3)
(0, (1, (1, None)))
>>> fib_sequence(4)
(0, (1, (1, (2, None))))
>>> fib_sequence(5)
(0, (1, (1, (2, (3, None)))))


The above program provides representation as (element, restOfTheList).

We have this sequence containers in Python:

>>> tuple =  (1, 2, 3, 4)
>>> r = range(1,5)
>>> str = '1234'


Is the representation of the aforementioned Python sequence containers same as the above representation of the Fibonacci sequence abstraction?

If no, can we make the representation of the Fibonacci sequence abstraction better, basically to forward this sequence for further processing by sequence processing functions like map() filter() sum() etc.?

You should call rlist() consistently, and write

elif k == 1:
return rlist(curr, empty_rlist)


… for reasons that will become apparent. Also be sure to use four spaces per level of indentation, as prescribed by PEP 8.

Are your tuple, range, and string the same as each other? No, comparing them using == will obviously return False. What they all have in common, though, is that they are all iterables. Being iterable means that you can use them in for e in iterable expressions — either in a loop or a generator.

That means that if you want to be able to write things like print([e for e in fib_sequence(5)]), you'll need to make your rlist type iterable. Here's one way you could accomplish that.

class rlist(tuple):
def __new__(cls, first, rest):
return super(rlist, cls).__new__(cls, (first, rest))

def __iter__(self):
seq = self
while seq is not None:
yield first(seq)
seq = rest(seq)


This works as long as you have applied the rlist() fix to fib_sequence() as mentioned above.

• Note: iter(fib_sequence(0)) fails with TypeError: 'NoneType' object is not iterable. Suggestions for fixing that would be welcome. Commented Apr 6, 2015 at 11:32
• For your point: "comparing them using == will obviously return False", Who(object) owns this == functionality? How does that owner know about the representation aspect of these 3 abstractions to compare 3 sequence types? Because representation aspect of string/tuple/range abstraction would be different. Commented Apr 9, 2015 at 5:01
• Read about object.__eq__() Commented Apr 9, 2015 at 5:14
• Are map / filter / sum are also relying on this iterable concept to work seem less on string/tuple/range sequence type? Commented Apr 9, 2015 at 10:08
• The documentation says that map(), filter(), and sum() all accept iterables. Commented Apr 9, 2015 at 10:12

I'm no ninja coder, still though I know to handle myself. Your function does not need to take three arguments, you just need two. Avoid adding many conditions when iterating, it makes it slower. The most optimized solution I could find was this, is 10 times faster

def Fibonacci(n):
a,b=0,1
for i in range(n):
a, b = b, a+b
return a

• Sorry, what is ninja? Commented Apr 6, 2015 at 9:01
• The correct term is "killer coding ninja monkey guru handsome hero sexmachine." Commented Apr 6, 2015 at 9:08
• The original code returns the entire sequence up to that point; your solution returns just the last number. Commented Apr 6, 2015 at 10:01