我是新来的Haskell，我试图实现欧拉筛在流处理风格。
当我检查了关于素数的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)
它说
“ 双质数料在这里介绍，以防止不必要的记忆化，从而防止内存泄漏，按照梅丽莎奥尼尔的代码。 ”
怎么会这样？ 我无法弄清楚它是如何工作。
通常情况下，素数的定义埃拉托色尼的筛的理查德·伯德的配方流是自我指涉：
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
素数ps通过该定义产生被用作输入给它。 为了防止恶性循环的定义被灌注以初始值，2。这对应于埃拉托塞尼的筛作为发现在复合材料中，列举对每个素数p之间的间隙的素数的数学定义由P的步骤向上计数， P = {2} U（{3,4-，...} \∪{{P 2，P 2 + P，P 2 + 2P，...} | P P中}）。
所产生的流被用作在其自己的定义输入。 这使得质数的整个流的存储器中的保留（或大部分也无妨）。 这里的不动点是分享 ，corecursive：
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)
这个想法 （由于梅丽莎奥尼），那么，以分离此成两个流，具有内部循环送入素数的第二物流“上方”它：
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 = fx (gx)在这里被用作一个pointfree简写。）
有没有简单的办法解决第二个定义，即eulers 。
另外：你可以看到用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..]
