我是Haskell的新手，我正在尝试以流处理风格实现Euler's Sieve。
当我查看Haskell Wiki关于素数的页面时，我发现了一些神秘的流优化技术。 在3.8中 该维基的线性合并：
primesLME = 2 : ([3,5..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])
where
primes' = 3 : ([5,7..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])
joinL ((x:xs):t) = x : union xs (joinL t)
它说
">这里引入了双素数馈送，以防止不必要的 记忆，从而防止记忆泄漏，根据梅丽莎奥尼尔的 代码。
这怎么可能？我不知道它是如何工作的。
通常，理查德·伯德(Richard Bird)对埃拉托色尼筛子的表述中素数流的定义是自我指涉的：
import Data.List.Ordered (minus, union, unionAll)
ps = 2 : minus [3..] -- `:` is "cons"
(foldr (p r -> p*p : union [p*p+p, p*p+2*p..] r) [] ps)
此定义产生的素数ps用作其输入。为了防止恶性循环，定义以初始值 2 启动。这对应于埃拉托色尼筛子的数学定义，即在复合材料之间的间隙中找到素数，通过按 p 的步长计数来枚举每个素数 p，
P = { 2 }∪( {3,4,5，... } \⋃pinP{ p2， p 2+p，p2+2p， ... } )
生成的流在其自己的定义中用作输入。这会导致整个素数流在内存中保留(或大部分)。这里的固定点是共享，核心草书：
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)
这个想法(由于Melissa O'Neill)是，然后，将其分成两个流，一个内部循环馈送到"上方"的第二个素数流：
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)
因此，当ps2产生一些素数p时，它的内流xs的"核心">素数只需要实例化到大约sqrt p，任何由ps2产生的素数都可以被丢弃，并立即被系统收集垃圾：
\ \ <- PS2 <- 。 \ \ <- xs <-。 / \ \_________/
由内部循环xs产生的素数不能立即丢弃，因为它们是xs流本身所必需的。当xs产生了一个素数q时，只有它低于sqrt q的部分可以被丢弃，就在它被计算的foldr部分消耗之后。换句话说，这个序列将指针保留到其自身最大生产价值的sqrt(因为它被其消费者消费，如print)。
因此，对于一个馈送循环(带fix)，几乎整个序列都必须保留在内存中，而对于双馈送(带fix2)，只需要保留大部分内部循环，它最多只能达到主流产生的当前值的平方根。因此，整体空间复杂度从大约O(N)降低到大约O(sqrt(N))- 急剧降低。
为此，必须使用优化(即使用-O2开关)编译代码，并独立运行。您可能还必须使用-fno-cse开关。并且测试代码中必须只有一个对ps2的引用：
main = getLine >>= (read >>> (+(-1)) >>> (`drop` ps2) >>> print . take 5)
事实上，当在Ideone进行测试时，它确实显示出几乎恒定的内存消耗。
这是埃拉托色尼的筛子，而不是欧拉的筛子。
最初的定义是：
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..]
由于对倍数的过早处理，两者都非常低效。通过融合map和枚举到一个更远的枚举(从x到x*x，很容易补救第一个定义，即[x*x, x*x+x..])，以便可以推迟其处理 - 因为这里每个素数的倍数都是独立生成的(以固定间隔枚举)：
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"
这与本文顶部的鸟筛相同，分段：
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]]
((f <*> g) x = f x (g x)在这里用作无点速记。
第二个定义没有简单的解决方法，即eulers.
addition：你可以在这里看到用Python生成器实现的相同想法，为了进行比较。
事实上，Python代码采用了瞬时素数流的伸缩式、多级递归生产;在Haskell中，我们可以用非共享的多级定点组合器_Y来安排它：
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..]