User:WillNess: Difference between revisions

Latest revision as of 13:50, 21 February 2023

Monad is composable computation descriptions.

--   infinite folding due to Richard Bird
--   double staged primes production due to Melissa O'Neill
--   tree folding idea Heinrich Apfelmus / Dave Bayer 
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 via Y combinator

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, P = N_₂\N_₂_*N_₂ = N_₂\P_*N_₂ :

S = N_{2} ∖ ⋃_{p \in S} {p q : q \in N_{p}}

using standard definition

N_{k} = {n \in N : n \geq k}

. . . or,

N_{k} = {k} ⋃ N_{k + 1}

.

Trial division sieve is:

T = {n \in N_{2} : (\forall p \in T) (2 \leq p \leq \sqrt{n} \Rightarrow \neg (p ∣ n))}

If you're put off by self-referentiality, just replace $S$ or $T$ on the right-hand side of equations with $N_{2}$ , as the ancient Greeks might or mightn't have done, as well.

@@ Line 1: / Line 1: @@
-I'm interested in Haskell.
+[https://wiki.haskell.org/index.php?title=Monad&oldid=63472 Monad is composable computation descriptions].
-I like ''[http://ideone.com/qpnqe this]'':
+----
+I like ''[http://ideone.com/qpnqe this one-liner]'':
 <haskell>
---   inifinte folding idea due to Richard Bird
+--   infinite folding due to Richard Bird
---   double staged production idea due to Melissa O'Neill
+--   double staged primes production due to Melissa O'Neill
---   tree folding idea Dave Bayer / simplified formulation Will Ness
+--   tree folding idea Heinrich Apfelmus / Dave Bayer
-primes = 2 : g (fix g)
+primes = 2 : _Y ((3:) . gaps 5
-  where
+                      . foldi (\(x:xs) -> (x:) . union xs) []
-    g xs = 3 : gaps 5 (foldi (\(c:cs) -> (c:) . union cs)
+                      . map (\p-> [p*p, p*p+2*p..]))
-                             [[x*x, x*x+2*x..] | x <- xs])
-    gaps k s@(c:t)
+_Y g = g (_Y g)  -- multistage production via Y combinator
-       | k < c = k : gaps (k+2) s     -- minus [k,k+2..] (c:t), k<=c
-       | True  =     gaps (k+2) t     --   fused to avoid a space leak
-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 for better performance
+   | otherwise =     gaps (k+2) t     -- k==c
 </haskell>
 <code>foldi</code> is on [[Fold#Tree-like_folds|Tree-like folds]] page. <code>union</code> and more at [[Prime numbers#Sieve_of_Eratosthenes|Prime numbers]].
-The math formula for Sieve of Eratosthenes,
+The constructive definition of primes is the Sieve of Eratosthenes, '''P''' &nbsp;=&nbsp; '''N'''<sub><sub>2</sub></sub>\'''N'''<sub><sub>2</sub></sub><sub>*</sub>'''N'''<sub><sub>2</sub></sub> &nbsp;=&nbsp; '''N'''<sub><sub>2</sub></sub>\'''P'''<sub>*</sub>'''N'''<sub><sub>2</sub></sub> :
-::::<math>\textstyle\mathbb{S} = \mathbb{N}_{2} \setminus \bigcup_{p\in \mathbb{S}} \{n p:n \in \mathbb{N}_{p}\}</math>
-where
-::::<math>\textstyle\mathbb{N}_{k} = \{ n \in \mathbb{N} : n \geq k \}</math> &emsp; . . . or, &ensp;<math>\textstyle\mathbb{N}_{k} = \{k\} \bigcup \mathbb{N}_{k+1}</math> &emsp; :)&emsp;:) .
+::::<math>\textstyle\mathbb{S} = \mathbb{N}_{2} \setminus \bigcup_{p\in \mathbb{S}} \{p\,q:q \in \mathbb{N}_{p}\}</math>
+using standard definition
+::::<math>\textstyle\mathbb{N}_{k} = \{ n \in \mathbb{N} : n \geq k \}</math> &emsp; . . . or, &ensp;<math>\textstyle\mathbb{N}_{k} = \{k\} \bigcup \mathbb{N}_{k+1}</math> .
-Trial division sieve:
+Trial division sieve is:
-::::<math>\textstyle\mathbb{T} = \{n \in \mathbb{N}_{2}: (\not\exists p \in \mathbb{T}) (p\leq \sqrt{n}\,, p\mid n)\}</math>
+::::<math>\textstyle\mathbb{T} = \{n \in \mathbb{N}_{2}: (\forall p \in \mathbb{T})(2\leq p\leq \sqrt{n}\, \Rightarrow \neg{(p \mid n)})\}</math>
-If you're put off by self-referentiality, just replace <math>\mathbb{S}</math> or <math>\mathbb{T}</math> on the right-hand side of equations with <math>\mathbb{N}_{2}</math>.
+If you're put off by self-referentiality, just replace <math>\mathbb{S}</math> or <math>\mathbb{T}</math> on the right-hand side of equations with <math>\mathbb{N}_{2}</math>, as the ancient Greeks might or mightn't have done, as well.