StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
13895347
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
4
CommunityOwnedDate
CreationDate
2012-12-15T19:18:23.083
FavoriteCount
0
LastActivityDate
2017-06-20T17:18:20.540
LastEditDate
2017-06-20T17:18:20.540
LastEditorUserId
849891
OwnerUserId
849891
ParentId
13894417
PostTypeId
2
Score
9
ViewCount
0
LastEditorDisplayName
text
Body
Normally, definition of primes stream in Richard Bird's formulation of the sieve of Eratosthenes is self-referential: <pre><code>import Data.List.Ordered (minus, union, unionAll) ps = ((2:) . minus [3..] . foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r) []) ps </code></pre> The primes <code>ps</code> produced by this definition are used as input to it. To prevent a vicious circle the definition is primed with the initial value, 2. This corresponds to the mathematical definition of the sieve of Eratosthenes as finding primes in the gaps between the composites, enumerated for each prime p by counting up in steps of p, P = {2} U ({3,4,...} \ U {{p2, p2+p, p2+2p, ...} | p in P}). The produced stream is used as input in its own definition. This causes the retention of the whole stream of primes in memory (or most of it anyway). The fixpoint here is sharing, corecursive: <pre><code>fix f = xs where xs = f xs -- a sharing fixpoint combinator ps = fix ((2:) . minus [3..] . foldr (...) []) -- = xs where xs = 2 : minus [3..] (foldr (...) [] xs) </code></pre> <hr> The idea (due to Melissa O'Neill) is, then, to separate this into two streams, with an inner loop feeding into the second stream of primes "above" it: <pre><code>fix2 f = f xs where xs = f xs -- double-staged fixpoint combinator ps2 = fix2 ((2:) . minus [3..] . foldr (...) []) -- = 2 : minus [3..] (foldr (...) [] xs) where -- xs = 2 : minus [3..] (foldr (...) [] xs) </code></pre> Thus, when <code>ps2</code> produces some prime <code>p</code>, its inner stream <code>xs</code> of "core" primes needs only be instantiated up to about <code>sqrt p</code>, and any primes which are produced by <code>ps2</code> can get discarded and garbage-collected by the system immediately afterwards: <pre> \ \ <- ps2 <-. \ \ <- xs <-. / \ \_________/ </pre> Primes produced by the inner loop <code>xs</code> can not be immediately discarded, because they are needed for <code>xs</code> stream itself. When <code>xs</code> has produced a prime <code>q</code>, only its part below <code>sqrt q</code> can be discarded, just after it has been consumed by the <code>foldr</code> part of the computation. In other words this sequence maintains back pointer into itself down to the <code>sqrt</code> of its biggest produced value (as it is being consumed by its consumer, like <code>print</code>). So with one feed loop (with <code>fix</code>) almost the whole sequence would have to be retained in memory, while with the double feed (with <code>fix2</code>) only the inner loop needs to be mostly retained that only reaches up to the square root of the current value produced by the main stream. Thus the overall space complexity is reduced from about O(N) to about O(sqrt(N)) -- a drastic reduction. For this to work the code must be compiled with optimizations, i.e. with the <code>-O2</code> switch, and run standalone. You may also have to use <code>-fno-cse</code> switch. And there must be only one reference to <code>ps2</code> in the testing code: <pre><code>main = getLine >>= (read >>> (+(-1)) >>> (`drop` ps2) >>> print . take 5) </code></pre> In fact, when tested at Ideone, <a href="http://ideone.com/p0e81" rel="nofollow noreferrer">it does show</a> a practically constant memory consumption. <hr> And it's the Sieve of Eratosthenes, not Euler's sieve. The initial definitions are: <pre><code>eratos (x:xs) = x : eratos (minus xs $ map (*x) [x..] ) -- ps = eratos [2..] eulers (x:xs) = x : eulers (minus xs $ map (*x) (x:xs)) -- ps = eulers [2..] </code></pre> Both are very inefficient because of the premature handling of the multiples. It is easy to remedy the first definition by fusing the <code>map</code> and the enumeration into one enumeration moved further away (from <code>x</code> to <code>x*x</code>, i.e. <code>[x*x, x*x+x..]</code>), so that its handling can be postponed -- because here each prime's multiples are generated independently (enumerated at fixed intervals): <pre><code>eratos (p:ps) xs | (h,t) <- span (< p*p) xs = -- ps = 2 : eratos ps [2..] h ++ eratos ps (minus t [p*p, p*p+p..]) -- "postponed sieve" </code></pre> which is the same as Bird's sieve at the top of this post, segment-wise: <pre><code>ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2) <*> inits) ps, n <- [r+1..q-1] `minus` foldr union [] [[s+p, s+2*p..q-1] | p <- px, let s = r`div`p*p]] </code></pre> (<code>(f <*> g) x = f x (g x)</code> is used here as a <a href="/questions/tagged/pointfree" class="post-tag" title="show questions tagged 'pointfree'" rel="tag">pointfree</a> shorthand.) There is no easy fix for the second definition, i.e. <code>eulers</code>. <hr> addition: you can see the same idea implemented with Python generators, for comparison, <a href="https://stackoverflow.com/a/10733621/849891">here</a>. In fact, that Python code employs a telescopic, multistage recursive production of ephemeral primes streams; in Haskell <a href="http://ideone.com/se0bsB" rel="nofollow noreferrer">we can arrange for it</a> with the non-sharing, multi-staged fixpoint combinator <code>_Y</code>: <pre><code>primes = 2 : _Y ((3:) . sieve 5 . unionAll . map (\p -> [p*p, p*p+2*p..])) where _Y g = g (_Y g) -- == g . g . g . g . .... sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- == [k,k+2..] \\ s, | True = sieve (k+2) xs -- when s ⊂ [k,k+2..] </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POdouble stream feed to prevent unneeded memoization?
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USWill Ness
UserOwnerUserId
1. USWill Ness
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POdouble stream feed to prevent unneeded memoization?
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.