Sequence generation problem - Fibonacci

Question

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

Answer 1

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.

• 200_success: Note: iter(fib_sequence(0)) fails with TypeError: 'NoneType' object is not iterable. Suggestions for fixing that would be welcome.
• overexchange: 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.
• 200_success: Read about object.__eq__()
• overexchange: Are map / filter / sum are also relying on this iterable concept to work seem less on string/tuple/range sequence type?
• 200_success: The documentation says that map(), filter(), and sum() all accept iterables.

Answer 2

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

• overexchange: Sorry, what is ninja?
• Juanvulcano: The correct term is "killer coding ninja monkey guru handsome hero sexmachine."
• 200_success: The original code returns the entire sequence up to that point; your solution returns just the last number.