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