Why should I switch to Python? - Infinity of Primes

Tim Peters tim_one at email.msn.com
Thu Apr 6 08:09:59 CEST 2000


[Harald Hanche-Olsen]
> ...
> Since this is a posted to a computer language group, after all, I
> include my own simple implementation of the Sieve in Haskell:
>
> primes :: [Integer]
> primes = 2 : ([3..] `except` composites)
>
> composites :: [Integer]
> composites  = flatten (map (\ p -> [p*p, p*(p+1)..]) primes)
>
> union :: [Integer] -> [Integer] -> [Integer]
> xl@(x:xs) `union` yl@(y:ys) | x<y       = x : xs `union` yl
>                             | x>y       = y : xl `union` ys
>                             | otherwise = x : xs `union` ys
>
> except :: [Integer] -> [Integer] -> [Integer]
> xl@(x:xs) `except` yl@(y:ys) | x<y       = x : xs `except` yl
>                              | x==y      = xs `except` ys
>                              | otherwise = xl `except` ys
>
> flatten :: [[Integer]] -> [Integer]
> flatten ((x:xs):zz) = x : xs `union` (flatten zz)
>
> I wonder if someone can come up with an equally immediate solution
> (i.e., a straight translation from the mathematical formulation) in
> python?

Hmm.  Try out this one-liner Haskell defn, which is so pretty it *should*
bring tears of joy to everyone's eyes <blink>:

primes = sieve [2..]
    where sieve (p:rest) = p : sieve [n | n <- rest, mod n p /= 0]

Within the last month or two I posted a Python version of that under subject
"Fun w/ Lazy Streams".  Given general machinery for supporting lazy streams
(see the thread), the sieve example ended up looking like:

def removemults(s, n):   # s but without any multiples of n
    def notdivisible(i, n=n):
        return i % n
    return sfilter(s, notdivisible)

def sieve(s):
    return Stream(s.head(),
                  lambda s=s:
                      sieve(removemults(s.tail(), s.head())))

primes = sieve(srange(2))

That's approximately as irritating as it is in Scheme, were laziness also
needs to be faked.

> Indeed, I would be tempted to say that Haskell is better suited for
> learning (some kinds of) mathematics than python.
>
> but-I-wouldn't-dare-say-so-in-comp.lang.python-ly y'rs,

I would -- I've often recommended Haskell here.  Learning to think in a
purely functional way is really helpful, right up until it get
counterproductive <wink>.

if-god-intended-us-to-use-functional-languages-he-wouldn't-have-
    created-guido-ly y'rs  - tim






More information about the Python-list mailing list