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 one-liner:
-- infinite folding idea due to Richard Bird
-- double staged production idea due to Melissa O'Neill
-- tree folding idea Dave Bayer / improved tree structure
-- Heinrich Apfelmus / simplified formulation Will Ness
primes = 2 : _Y ((3:) . gaps 5
. foldi (\(x:xs) -> (x:) . union xs) []
. map (\p-> [p*p, p*p+2*p..]))
_Y g = g (_Y g) -- multistage production
gaps k s@(c:t) -- == minus [k,k+2..] (c:t), k<=c,
| k < c = k : gaps (k+2) s -- fused for better performance
| otherwise = gaps (k+2) t -- k==c
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.