Haskell生成第10001个素数：两种调用方式的性能差异疑问

我们在用Haskell完成Project Euler第7题「找出第10001个素数」时，实现了一个基于过滤的简单素数生成算法：

primes = filterPrime [2..]
  where filterPrime (p:xs) =
          p : filterPrime [x | x <- xs, x `mod` p /= 0]

遇到了一个奇怪的现象：在GHCi中直接输入primes，让它输出直到数字超过10万左右再停止，整个过程耗时约3秒；但直接调用primes !! 10001来获取第10001个素数，却要耗时20-25秒。而一旦列表生成完成（比如刚才打印过primes之后），两种方式获取第10001个元素都能瞬间返回。

核心原因分析 #

1. 惰性求值与列表缓存机制

Haskell是惰性求值语言，primes是一个无限惰性列表——只有当需要使用元素时，才会逐步计算并生成。在GHCi中直接打印primes时，程序会不断生成素数并输出，直到你手动停止。这个过程中，已经生成的所有素数都会被缓存下来（GHCi会保留这些计算结果，避免重复计算）。当你停止时，缓存里已经包含了第10001个素数（第10001个素数是104743，超过10万），所以之后再获取这个元素自然是瞬间返回。

而直接调用primes !! 10001时，程序需要从头开始，逐个计算素数，直到数到第10001个。这个过程中没有提前生成的缓存可以复用，所有计算都要从头来过。

2. 这个筛法的低效性

我们实现的并不是真正的埃拉托斯特尼筛，而是一个朴素的过滤筛——每个新素数p都会创建一个新的过滤层，对后续所有数检查是否能被p整除。比如数字15，会被素数3过滤一次，还会被素数5再检查一次（虽然此时它已经被过滤掉了）。这种重复检查会随着素数数量的增加，带来指数级的开销。

当直接打印primes到10万以上时，虽然看起来输出的数字范围大，但生成素数的过程是连续的，每个过滤层的计算是随着元素生成逐步完成的；而!! 10001需要精确停在第10001个素数，这个素数本身是104743，计算到它需要让前面所有10000个素数的过滤层都处理到这个数，每个过滤层的取模检查都会累积开销，最终导致总耗时远高于连续打印的情况。

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