functional programming

[Michael Hudson]

Gerrit Holl <gerrit.holl at pobox.com> writes:

> <quote name="Remco Gerlich" date="951294162">
> > Michal Wallace (sabren) wrote in comp.lang.python:
> > > I guess my original question had to do with what functional
> > > programming looks like in the wild, and what it might look like in
> > > python. Aahz posted a recursive version of a fib() routine. Is this
> > > not what you'd want? What would fib() look like in one of the
> > > functional languages you're used to?
> > 
> > Michael Hudson posted this little bit of Haskell last week:
> > 
> > fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]
> > 
> > I can't translate that to anything resembling Python at all. I don't
> > know if list comprehensions in Python will be/are this powerful.
> 
> Well, you can just write a class doing it.
> 
> # pseudo-code
> def fib(...):
>    ...
> 
> class Fibonacci:
>     def __getslice__(self, start, stop):
>         return fib(start, stop)
> 
>     def __getitem__(self, item):
>         return fib(0, item)
> 
>     ...
> 

I think you have missed the point.  And I doubt list comprehensions
can be this powerful in Python without lazy evaluation.

A more direct Python version would be along the lines of:

class Fib:
    def __init__(self):
        self.answers = {0:1L,1:1L}
    def __getitem__(self,item):
        if self.answers.has_key(item):
            return self.answers[item]
        else:
            val = self[item-2] + self[item-1]
            self.answers[item] = val
            return val

This is /reasonably/ quick; but obviously

def ffib(n):
    a,b=1L,1L
    for i in xrange(n-1):
        t=a+b; b=a; a=t
    return a

is faster.

Cheers,
M.

-- 
very few people approach me in real life and insist on proving they are
drooling idiots.                         -- Erik Naggum, comp.lang.lisp