Talk:Sieve of Eratosthenes (Haskell)
From LiteratePrograms
Is there any way we can convince the maintainer of the site to include a ghc installation behind the scenes so errors like the previous versions of this page can be caught without releasing incorrect code to the wild?
---
I don't know whether this is of any interest to this site, but replacing:
... foldr1 f ... where f (x:xs) ys = x : (merge xs ys)
with
mergeAllLogarithmic ((x:xs):ys) =
x : merge xs (mergeAllLogarithmic (twomap ys)) where
twomap (x1:x2:xs) = (merge x1 x2) : twomap xs
and some adjustment to primes results in a significant speedup, I'm guessing reducing a linear factor to a logarithmic one. I guess its fairly opaque though...
[edit]
Inaccuracies
In the description for first implementation (described by the author as "naive"):
- primes is not a function; it is the variable holding infinite list of primes itself
- sieve is not tail-recursive: it performs an additional computation (consing) to the
recursive result!
