Haskell中引用透明性困惑：埃氏筛实现栈溢出问题

你遇到的核心问题是纯函数的引用透明性与Haskell惰性求值、共享机制的交互，并非引用透明性失效，而是求值过程中缺乏共享导致的栈溢出。下面逐一拆解：

问题核心：重复调用的非共享求值 #

先看你的原代码：

ndnp :: Integer -> [Integer]
ndnp 0 = [2..]
ndnp n = [n | n <- (ndnp (n-1)), mod n (head $ ndnp (n-1)) /= 0]

而手动定义的nums1是：

nums1 = [n | n <- nums0, mod n (head nums0) /= 0]
nums0 = [2..]

两者逻辑上等价，但行为不同的关键在于共享机制：

• nums1中的nums0是顶级绑定，属于CAF（Constant Applicative Form），Haskell会自动共享它的求值结果——所有对nums0的访问都会复用同一个无限列表thunk，head nums0只需要计算一次（得到2），后续所有guard检查都会直接复用这个值。
• 原ndnp 1中的两次ndnp (n-1)（即ndnp 0）是独立的函数调用，除非编译器做了公共子表达式消除（CSE），否则会生成两个完全独立的列表thunk。虽然它们的结果等价，但求值时不会共享任何中间结果。

栈溢出的具体原因 #

当调用take 10 $ ndnp 1时，求值过程会重复触发以下步骤：

1. 遍历ndnp 0的元素，逐个检查mod n (head $ ndnp 0) /= 0；
2. 每次检查guard时，都要重新计算head $ ndnp 0——虽然ndnp 0是[2..]，head是2，但每次调用都会生成新的thunk并求值；
3. 对于更深层次的递归（比如ndnp 2），问题会被放大：每次检查guard都要重新计算head $ ndnp 1，而ndnp 1本身需要遍历ndnp 0过滤元素，这会导致递归求值的栈帧不断累积，最终超出栈限制引发溢出。

而赋值a = ndnp 1正常，是因为惰性求值下，赋值操作只是创建了一个未求值的thunk，只有当你尝试访问a的元素时，才会触发实际计算。

修复代码的原理：通过绑定实现共享 #

修复后的代码用where绑定将ndnp (n-1)赋值给arr：

ndnp :: Integer -> [Integer]
ndnp 0 = [2..]
ndnp n = [n | n <- arr, mod n (head $ arr) /= 0]
     where arr = ndnp (n-1)

这里的关键是强制共享：数据源和guard中使用的是同一个arr thunk，所有对arr的访问都会复用已经求值的部分——比如head arr只需要计算一次，后续所有guard检查都会直接复用这个结果，避免了重复求值和栈帧累积。

关于引用透明性的澄清 #

引用透明性的定义是：如果y = f(x)，那么任何出现f(x)的地方都可以替换为y，而不改变程序的最终输出结果。它保证的是结果等价，而非求值过程、效率或资源使用的一致性。

你的原代码中，两次ndnp(n-1)的结果是等价的，将它们替换为同一个arr完全符合引用透明性；修复后的代码只是优化了求值过程，并没有改变最终输出的结果，因此并没有违反引用透明性。

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