can Python be useful as functional?

[Bruno Desthuilliers]

Lorenzo Stella a écrit :
> 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;

Not exactly. They are used quite a lot, yes, but that's also the case in 
other paradigms. What's important in functional programming is *functions*.

> 2) any "cycle" in FP become
> recursion.

FP idioms tends to use recursion instead of iteration, yes. But that's 
only viable with implementations doing tail-recursion optimisation - 
which is not the case with CPython (not that it couldn't FWIW - it's a 
design choice, and one of the few I don't necessarily agree with).

> I also know that Python got some useful tool such as map, filter,
> reduce... 

And all there itertools versions...

> so I told: "let's try some FP-style programming with
> Python!". 

Most of the functional constructs that makes sens in Python are already 
idiomatic. And some common functional stuff are better reimplemented the 
pythonic way - as an example, while partial application is usually 
implemented with closures, and *can* indeed be implemented that way in 
Python, the class-based implementation is IMHO much better.

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

Strictly speaking, a language is functional if it has functions as first 
class objects. Period. According to this definition, Python is a 
functional language. Now that doesn't mean you should try to write 
Haskell in Python... IOW, your code is not "wrong", but it's certainly 
not the best way to implement such an algorithm in Python.