User:WillNess
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
A perpetual Haskell newbie. I like this semi-one-liner:
-- inifinte folding idea due to Richard Bird
-- double staged production idea due to Melissa O'Neill
-- tree folding idea Dave Bayer / simplified formulation Will Ness
primes = 2 : g (fix g)
where
g xs = 3 : gaps 5 (foldi (\(c:cs) -> (c:) . union cs) []
[[x*x, x*x+2*x..] | x <- xs])
fix g = xs where xs = g xs -- global defn to avoid space leak
gaps k s@(c:t) -- == minus [k,k+2..] (c:t), k<=c,
| k < c = k : gaps (k+2) s -- fused to avoid a space leak
| True = gaps (k+2) t
foldi
is on Tree-like folds page. union
and more at Prime numbers.
The constructive definition of primes is the Sieve of Eratosthenes:
using standard definition
- . . . or, :) :) .
Trial division sieve is:
If you're put off by self-referentiality, just replace or on the right-hand side of equations with , but even ancient Greeks knew better.