Haskell自引用素数列表生成代码挂起问题咨询

核心原因：惰性求值下的循环依赖 #

你的问题出在自引用素数列表时的循环依赖，结合Haskell的惰性求值特性，导致程序陷入死锁：

1. is_prime通过takeWhile (smaller_than_sqrt p)从传入列表筛选符合条件的数，再检查这些数都不整除p。
2. 当使用primes = 2 : 3 : [ p | p <- [5..], is_prime p primes]时，生成第三个素数（5）需要先执行is_prime 5 primes。
3. 计算is_prime 5 primes时，isqrt 5 = ceiling(sqrt(5)) = 3，所以smaller_than_sqrt 5 x的条件是x <= 3：
   • primes的前两个元素2、3都满足条件，会被保留；
   • 接下来需要检查primes的第三个元素（正在生成的5）是否满足x <=3，但这个元素的生成恰好依赖当前is_prime 5 primes的计算结果——形成循环等待：生成第三个素数需要先完成素数检查，而素数检查又需要第三个素数的值来判断是否停止遍历，最终导致程序挂起或触发循环错误。

而is_prime p [2..]能正常运行，是因为[2..]是独立的无限列表，元素可直接生成，不需要依赖当前素数计算。当takeWhile遇到第一个大于3的元素（4）时，会立即停止遍历，不会触发循环依赖。

修复方案：优化素数判断的终止条件 #

素数判断的关键优化：只需要检查到素数的平方大于p即可。如果p有一个大于sqrt(p)的因数，对应的另一个因数必然小于sqrt(p)，而这个小因数的素因子已经被检查过了。

修改代码如下：

main = do
    print (smaller_than_sqrt 4 2)
    print (smaller_than_sqrt_list 5 [2..])
    print ("5")
    print (is_prime 5 [2..])
    print ("7")
    print (is_prime 7 [2..])
    print ("9")
    print (is_prime 9 [2..])
    print ("test")
    print (take 5 primes) -- 现在可正常运行

-- Integer square root（原代码保留，修改后实际不再依赖此函数）
isqrt :: Int -> Int
isqrt = ceiling . sqrt . fromIntegral

-- 优化终止条件：检查x的平方是否小于等于p
smaller_than_sqrt :: Int -> Int -> Bool
smaller_than_sqrt p x = x * x <= p

not_divides :: Int -> Int -> Bool
not_divides p x = p `mod` x /= 0

smaller_than_sqrt_list :: Int -> [Int] -> [Int]
smaller_than_sqrt_list p xs = takeWhile (smaller_than_sqrt p) xs

is_prime :: Int -> [Int] -> Bool
is_prime p xs = all (not_divides p) (smaller_than_sqrt_list p xs)

-- 修复后的自引用素数列表
primes = 2 : 3 : [ p | p <- [5..], is_prime p primes]

修改后，检查p=5时，x*x <=5仅匹配2（2²=4≤5），3²=9>5，takeWhile取完2后就停止遍历，不会请求primes的第三个元素，循环依赖被打破，素数列表可正常生成。

验证效果 #

运行修改后的代码，take 5 primes会输出[2,3,5,7,11]，符合预期。

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