4 ms·
I am pretty sure the sieve can be written like this in Haskell, which might be a bit short for a research paper: sieve :: Integral a => a -> [a] sieve
by ahakki 9y ago
I am pretty sure the sieve can be written like this in Haskell, which might be a bit short for a research paper:
sieve :: Integral a => a -> [a]
sieve l =
sieve' [2..l] []
where
sieve' (p:ns) ps =
sieve' (filter (\x -> rem x p /= 0) ns) (p : ps)
sieve' [] ps =
reverse ps
- adamwk 9y agoThat's not the real sieve, though. It doesn't cross off pre-visited primes and is incredibly inefficient. Try finding just the 19th prime. Here is the paper on the real sieve, https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
- Confusion 9y agoAnd it's exactly the same thing with the classical beautiful functional example of quicksort. It's not actually quicksort and its performance is awful as a result. Haskell has trade offs.
- hzhou321 9y agoSome ideas on how to make it into a research paper -- add discussion on how do you trivially manage memory (avoid unnecessary allocation and copying and reversing). The original trivia idea was simply to sieve in place. So how do we do that in Haskell (hint: invent something)?