Re: can Python be useful as functional?

[Paul Rudin]

Lorenzo Stella <[EMAIL PROTECTED]> writes:

> Hi all,
> I haven't experienced functional programming very much, but now I'm
> trying to learn Haskell and I've learned that: 1) in functional
> programming LISTS are fundmental; 2) any "cycle" in FP become
> recursion.
> I also know that Python got some useful tool such as map, filter,
> reduce... so I told: "let's try some FP-style programming with
> Python!". I took a little example of Haskell:
>
>      listprimes :: Integer -> [Integer]
>      listprimes n = if n == 0 then sieve [2..] else sieve [2..(n-1)]
> where
>             sieve [] = []
>             sieve (p:xs) = p : sieve (filter (\x -> mod x p > 0) xs)
>
> and I tried to "translate" it in Python:
>
>      def sieve(s):
>          if s == []:
>              return []
>          else:
>              return [s[0]] + sieve(filter((lambda x: x % s[0] > 0),
> s[1:]))
>
>      def listprimes(n):
>          return sieve(range(2,n))
>
> These should be almost the same: listprimes actually lists prime
> integers up to n-1. The result is: Haskell implementation works well,
> maybe it's not the better way to do it, but it does what I wanted.
> Python implementation gives me
>
>      RuntimeError: maximum recursion depth exceeded in cmp
>
> My question is: how can we call a language "functional" if it's major
> implementation has a limited stack? Or is my code wrong?

It's no tthat it's "wrong", but doing recursion in python can be
problematic because there's no tail recursion optimisation and the
size of the stack is limited (so eventually you'll run out of stack if
you recurse deep enough).

One way to capture the spirit of that Haskell program in Python is to
use things from itertools; something like this (modified from
<http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117119>):


import itertools
def listprimes(n):

    def sieve(nums):
        seq = nums
        while True:
            prime = seq.next()
            seq = itertools.ifilter(prime.__rmod__, seq)
            yield prime

    if n == 0:
        return sieve(itertools.count(2))
    else:
        return sieve(itertools.islice(itertools.count(2), n-1))

>>> list(listprimes(100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
73, 79, 83, 89, 97]

-- 
http://mail.python.org/mailman/listinfo/python-list