我有一个简单的玩具示例，它似乎不同意垃圾收集器关于什么样的数据结构可以被回收（也称为内存泄漏）。我并不是想提出这个算法的内存效率更高的版本（这里有一个更好的算法集合：Haskell Wiki - Prime numbers，而是一个解释，为什么垃圾收集器没有识别列表中旧的、超出范围的和未使用的部分来回收内存。
代码在这里：
import Data.List (foldl')
erat' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat' (c,b) ((x,y):xs)
| c < x = (x,y) : erat' (c,b) xs
| c == x = (x+y,y) : erat' (c,True) xs
| c > x = (x+y,y) : erat' (c,b) xs
erat' (c,b) []
| b = []
| otherwise = [(c,c)]
erat :: [Integer] -> [(Integer,Integer)]
erat = foldl' (\a c -> erat' (c,False) a) []
primes :: Integer -> [Integer]
primes n = map snd $ erat [2..n]
本质上，用正整数调用素数将返回一个包含该数在内的所有素数的列表。将素数对及其高水位线倍数的列表传递给erat'，同时传递一对素数，其中包括候选素数和布尔值（对于素数为false，对于非素数为true）。对erat'的每一个非递归调用都会传递一个新列表，我希望输出最多包含从列表开始到第一次更改点的某些共享单元格。
一旦传递给erat的列表中修改过的单元格超出范围，内存就应该被标记为要恢复，但是正如您所看到的，当您尝试使用足够大的数字（例如1000000）调用素数时，内存利用率会迅速飙升到数千万字节。
现在，问题是：为什么会这样世代垃圾回收器难道不应该侦测解除参考的清单储存格来回收它们吗？而且，它不应该很容易检测到他们没有参考文献，因为：
a）任何数据结构的引用都不能早于自身；
b）不能有新的引用，因为这些单元格/片段甚至不再是可引用数据结构的一部分，因为它超出了范围？
当然，可变的数据结构可以解决这个问题，但我觉得在这样的情况下，诉诸可变性会使haskell的一些理论原理落空。
感谢那些发表评论的人（特别是卡尔），我稍微修改了一下算法，增加了严格性（并且优化了开始跨越新素数的平方，因为更低的倍数也会被更低素数的倍数所跨越）。
这是新版本：
import Data.List (foldl')
erat' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat' (c,b) ((x,y):xs)
| c < x = x `seq` (x,y) : erat' (c,b) xs
| c == x = x `seq` (x+y,y) : erat' (c,True) xs
| c > x = x `seq` (x+y,y) : erat' (c,b) xs
erat' (c,b) []
| b = []
| otherwise = [(c*c,c)] -- lower multiples would be covered by multiples of lower primes
erat :: [Integer] -> [(Integer,Integer)]
erat = foldl' (\a c -> erat' (c,False) a) []
primes :: Integer -> [Integer]
primes n = map snd $ erat [2..n]
内存消耗似乎仍然相当大。此算法是否有任何其他更改可以帮助降低总内存利用率？
因为will指出我没有提供完整的统计数据，这些是上面列出的primes更新版本的运行数据，参数是100000：
在应用了所建议的更改之后，内存使用率现在大大降低了。例如，再看一次100000的素数运行：
最后，这是提议的变更合并后的最终准则：
import Data.List (foldl')
erat'' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat'' (c,b) ((x,y):xs)
| c < x = (x, y) : if x==y*y then (if b then xs
else xs++[(c*c,c)])
else erat'' (c,b) xs
| c == x = (x+y,y) : if x==y*y then xs
else erat'' (c,True) xs
| c > x = (x+y,y) : erat'' (c,b) xs
erat'' (c,True) [] = []
erat'' (c,False) [] = [(c*c,c)]
primes'' :: Integer -> [Integer]
primes'' n = map snd $ foldl' (\a c -> (if null a then 0 else
case last a of (x,y) -> y) `seq` erat'' (c,False) a) [] [2..n]
最后是1000000次的跑步，让你在新版本中感受到性能：
最佳答案
中断更新：您应该使用
map snd $ foldl' (\a c -> (if null a then 0 else
case last a of (x,y) -> y) `seq` erat' (c,False) a) [] [2..n]
在每次迭代中完全强制列表。它将consume less memory and run faster。
原因是
foldl'只会迫使蓄能器达到弱水头正常状态，即使使用last a也不够，因为它只会被强迫成一对(_,_)，而不会强迫其成分。但是当你的
erat'函数被改变，以便它尽快停止扫描素数及其倍数的中间列表，并尽可能地共享它的尾部（如下所述）时，即使使用更多的内存，它在不强制的情况下也会更快。你的（更新的）代码，为了易读性编辑了一点：
g :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
g (c,b) ((x,y):xs)
| c < x = (x, y) : g (c,b) xs -- `c < x` forces the x already,
| c == x = (x+y,y) : g (c,True) xs -- no need for `seq`
| c > x = (x+y,y) : g (c,b) xs
g (c,True) [] = []
g (c,False) [] = [(c*c,c)]
primes :: Integer -> [Integer]
primes n = map snd $ foldl' (\a c -> g (c,False) a) [] [2..n]
所以，您的
primes n实际上有点像反向[2..n]列表中的右折叠。为h写入flip $ foldl' (\a c -> g (c,False) a)，它是= map snd $ h [2..n] $ []
= map snd $ h [3..n] $ [(2*2,2)]
= map snd $ h [4..n] $ (4,2) :(g (3,False) [])
= map snd $ h [5..n] $ (4+2,2):(g (4,True ) $ g (3,False) [])
= map snd $ h [6..n] $ (6,2) :(g (5,False) $ g (4,True ) $ g (3,False) [])
....
由于蓄能器仅被强制到弱水头正常形式，因此
foldl'的严格性在这里的影响有限。用
(\a c -> last a `seq` g (c,False) a)折叠会给我们= map snd $ ... $ g (3,False) [(2*2,2)]
= map snd $ ... $ g (4,False) [(4,2),(3*3,3)]
= map snd $ ... $ g (5,False) [(4+2,2),(9,3)]
= map snd $ ... $ g (6,False) [(6,2),(9,3),(5*5,5)]
= map snd $ ... $ g (7,False) [(6+2,2),(9,3),(25,5)]
= map snd $ ... $ g (8,False) [(8,2),(9,3),(25,5),(7*7,7)]
= map snd $ ... $ g (9,False) [(8+2,2),(9,3),(25,5),(49,7)]
= map snd $ ... $ g (10,False) [(10,2),(9+3,3),(25,5),(49,7)]
= map snd $ ... $ g (11,False) [(10+2,2),(12,3),(25,5),(49,7)]
....
= map snd $ ... $ g (49,False)
[(48+2,2),(48+3,3),(50,5),(49,7),(121,11)...(2209,47)]
....
但是，所有这些更改都将被final
print推送到列表中，因此惰性不是这里的直接问题（它会导致较大输入的堆栈溢出，但这是次要的）。问题是，您的erat'（在上面重命名为g）最终会不必要地将每个条目推送到整个列表中，为每个候选号码重新创建整个列表这是一个非常繁重的内存使用模式。它应该尽早停止，并尽可能共享列表的尾部：
g :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
g (c,b) ((x,y):xs)
| c < x = (x, y) : if x==y*y then (if b then xs
else xs++[(c*c,c)])
else g (c,b) xs
| c == x = (x+y,y) : if x==y*y then xs
else g (c,True) xs
| c > x = (x+y,y) : g (c,b) xs
g (c,True) [] = []
g (c,False) [] = [(c*c,c)]
使用-O2编译并独立运行，it runs在~N1.9下，而不是原始函数的~ N，生成最多N个素数。
（当然，埃拉托色尼的一个“正常”筛选器应该运行在大约N1.1，理论上，它的理论时间复杂度是Nlog（log n））。