Haskell列表递归疑问：为何一种实现可行另一种陷入死循环？

熟悉Haskell的开发者大概率见过这种斐波那契数列实现：

fibs = 0:1:zipWith (+) fibs (tail fibs)

对这段代码的常见理解是：

• Haskell的惰性求值特性支持这种无限递归，不会产生问题
• Haskell的列表构造方式（首元素与剩余列表配对）意味着zipWith会在需要时计算出下一个元素
• 当zipWith参数中引用fibs时，它会使用当前已存在、未包含待计算新元素的列表

但下面这段素数生成代码却会陷入无限循环，无法生成素数列表：

main = print $ take 10 primes

dividesNone x ys = not $ any ((==0) . (x `mod`)) ys

primes = 2:[x | x <- [2..], x `dividesNone` primes]

即便尝试过用dropWhile和find的类似实现，结果依然相同。明明看起来逻辑合理，却无法正常运行，核心差异到底在哪里？

核心差异：递归引用的"可用列表"范围不同 #

先看斐波那契的实现：fibs的定义是0:1:zipWith (+) fibs (tail fibs)。当需要计算第三个元素时，zipWith用到的fibs是0:1:_，tail fibs是1:_——这两个列表的前两个元素已经是确定的，zipWith只需要取这两个列表的当前头部就能算出下一个值，完全不需要触及还未生成的部分。整个过程是递进式生成：每一步只依赖之前已经明确生成的元素，不会回溯或需要未生成的内容。

再看素数的实现：primes = 2:[x | x <- [2..], x dividesNone primes]。当尝试生成第二个素数（也就是列表里的第一个x）时，x从3开始，此时dividesNone 3 primes需要检查primes里的所有元素是否都不整除3。但primes此时是2:_，这个下划线代表的是还未生成的剩余素数列表。问题来了：any函数会遍历primes的所有元素，而primes的剩余部分是依赖当前这个x的生成的——这就形成了循环依赖：要生成primes的下一个元素，必须先确认x不被primes的所有元素整除，但primes的所有元素又包含还没生成的部分，而那些未生成的部分又需要当前x的判断结果才能继续生成，最终导致程序无限等待，陷入死循环。

简单说，斐波那契的递归只用到列表中已生成的前缀，而素数的实现试图用到列表的全部元素（包括未生成的），这在惰性求值下是无法推进的——因为any会一直遍历下去，永远等不到列表的结束（本来就是无限列表），而未生成的部分又依赖当前判断，形成死锁。

正确的素数生成（比如埃氏筛的惰性实现），会确保每次判断只用到已经生成的素数，而不是整个primes列表。比如：

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

这里每次筛选只用到当前的素数p，后续的筛选依赖已经过滤后的列表，不会出现循环依赖的问题。

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