Haskell实现埃拉托斯特尼筛法生成素数流失败求助

问题排查 #

代码卡在输出[2的核心原因是**minus函数的逻辑错误**，具体有两处：

1. 相等元素处理错误：当x == y时，原代码写的是x : minus xs ys，这会触发无限递归——每次都保留当前相等的元素，且递归时仍传入原列表，永远卡在同一个元素的比较上。比如处理到4时，[4,5,...]和[4,6,...]会一直重复比较4和4，无限生成4。
2. 大于分支逻辑错误：原代码在x > y时返回y : minus xs tys，这是把第二个列表的元素混入结果，但minus的语义是从第一个列表中移除第二个列表的元素，不是合并两个列表。
3. 缺少边界条件：未处理任一列表为空的情况，导致递归无法正常终止。

另外，原代码的unionP函数和union功能重复，属于冗余实现。

修复后的代码 #

-- 合并两个有序列表并去重（原逻辑正确，补充边界条件）
union :: Ord a => [a] -> [a] -> [a]
union xs@(x:txs) ys@(y:tys)
    | x < y     = x : union txs ys
    | x > y     = y : union xs tys
    | otherwise = x : union txs tys
union [] ys = ys
union xs [] = xs

-- 修正后的minus函数：从第一个列表中移除第二个列表的所有元素
minus :: Ord a => [a] -> [a] -> [a]
minus xs@(x:txs) ys@(y:tys)
    | x < y     = x : minus txs ys
    | x > y     = minus xs tys  -- 跳过第二个列表的当前元素，继续匹配
    | otherwise = minus txs tys  -- 相等时跳过该元素，处理剩余列表
minus [] _ = []
minus xs [] = xs

-- 合并多个有序列表（简化实现，直接用foldr union）
unionAll :: [[Integer]] -> [Integer]
unionAll = foldr union []

primes :: [Integer]
primes = 2 : ([3..] `minus` composites)
    where composites = unionAll [map (p*) [p..] | p <- primes]

-- 测试
firstPrimes = take 15 primes  -- 输出 [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

关键修复说明 #

1. 修正minus的核心逻辑：
   • 当x > y时，跳过第二个列表的当前元素，继续用原第一个列表和第二个列表的剩余部分递归
   • 当x == y时，跳过该元素，用两个列表的剩余部分递归，确保移除重复元素
2. 补充边界条件：处理任一列表为空的情况，保证递归能正常终止
3. 简化unionAll：直接用foldr union []替代冗余的unionP实现，更贴合语义

测试验证 #

运行修正后的代码，firstPrimes会正确输出前15个素数，不会再出现卡住的情况。

内容的提问来源于stack exchange，提问作者teo