current community

your communities

more stack exchange communities

Stack Exchange
tour help
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.
up vote 1 down vote favorite

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

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
Note: iter(fib_sequence(0)) fails with TypeError: 'NoneType' object is not iterable. Suggestions for fixing that would be welcome. –  200_success♦ Apr 6 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. –  overexchange Apr 9 at 5:01
    
Read about object.__eq__() –  200_success♦ Apr 9 at 5:14
    
Are map / filter / sum are also relying on this iterable concept to work seem less on string/tuple/range sequence type? –  overexchange Apr 9 at 10:08
    
The documentation says that map(), filter(), and sum() all accept iterables. –  200_success♦ Apr 9 at 10:12
up vote -3 down vote

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
share|improve this answer
    
Sorry, what is ninja? –  overexchange Apr 6 at 9:01
1  
The correct term is "killer coding ninja monkey guru handsome hero sexmachine." –  Juanvulcano Apr 6 at 9:08
2  
The original code returns the entire sequence up to that point; your solution returns just the last number. –  200_success♦ Apr 6 at 10:01

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.