haskell - Haskell 中的引用透明度困惑

Question

首先，尽管这是埃拉托斯特尼筛法的实现，但这不是一个家庭作业问题。我可以在许多介绍性书籍中找到 Sieve 的实现:)。

我的问题是我对引用透明性的困惑，这是函数式编程的优点之一。

我的理解是，我可以用 y 替换程序中任何位置的 f(x)，前提是 y = f(x) 并且我使用的是纯函数。

使用筛子“手动”实现第 n 个素数的简单实现是

nums0 = [2..]  -- allowed by lazy evaluation
nums1 = [n | n <- nums0, mod n (head nums0) /= 0] -- works, gives [3,5,7,9,11,13,15...]
nums2 = [n | n <- nums1, mod n (head nums1) /= 0] -- works, gives [5,7,11,13,...]
nums3 = [n | n <- nums2, mod n (head nums2) /= 0] -- works, gives [7,11,13,...]

很明显，这里存在递归模式。让我们调用 ndnp m 函数，该函数返回大于 1 且不能被前 m 个素数整除的自然数列表，即

nums0 = ndnp 0  -- (i.e. all numbers starting at 2)
nums1 = ndnp 1  -- (not divisible by 2)
nums2 = ndnp 2  -- (not divisible by 2 or 3)

要找到第 N 个素数，我们可以简单地执行 head $ ndnp (n-1)。

构建numsX数组的示例具有递归结构:

-- ndnp: Not Divisible by first N Primes
ndnp :: Integer -> [Integer]
ndnp 0 = [2..]
ndnp n = [n | n <- (ndnp (n-1)), mod n (head $ ndnp (n-1)) /= 0]

特别是，ndnp 1 是由 ndnp 0 或 nums0 构建的

当运行take 10 $ ndnp 0时，我得到了我期望的答案。当我运行 take 10 $ ndnp 1 时，我得到了一个 stackoverflow。

我的问题:

• 我可以很好地分配:a = ndnp 1 是合法的。评估是懒惰的，我理解。
• 当我尝试 take 时，出现堆栈溢出(这表明它正在尝试评估整个结构)。我可以理解是否 mod 或其他强制急切求值的东西，但我知道情况并非如此，因为......
• take 10 nums1 工作得很好，它是基于循环无限、惰性求值列表的相同步骤构建的!
• 既然nums0 = ndnp 0，为什么take 10 $ nums1的执行很好(它使用nums0并迭代它)，但是 take 10 $ ndnp 1 损坏了(它使用 ndnp 0 的结果并对其进行迭代)？引用透明度表明我应该能够将其中一个替换为另一个，但在一种情况下我保留惰性求值，而另一种会产生堆栈溢出!

注意: 我找到了一个解决方案

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

这使我的代码可以工作，但并不能让我很好地理解何时具有引用透明度以及何时不具有引用透明度。

Answer 1

如果您打开了警告(这是一个很好的做法 - 对我来说这有点神秘，包括 GHC 在内的许多编译器默认不打印警告)，那么您会看到像这样:

Referential.hs:6:15: warning: [-Wname-shadowing]
    This binding for ‘n’ shadows the existing binding
      bound at Referential.hs:6:6
  |
6 | ndnp n = [n | n <- (ndnp (n-1)), mod n (head $ ndnp (n-1)) /= 0]
                  ^

这会告诉你出了什么问题。 Haskell 作用域规则意味着 ndnp 的原始定义相当于:

ndnp n = [m | m <- (ndnp (n-1)), mod m (head $ ndnp (m-1)) /= 0]
          ^   ^                      ^               ^

也就是说，您对 n 的新定义没有捕获 n 第一次出现的 ndnp (n- 1)，但它确实捕获了推导式中的所有其他 n。

当您尝试评估 ndnp 1 时，您会得到:

ndnp 1 = [m | m <- ndnp 0, mod m (head $ ndnp (m-1)) /= 0]

列表推导式以 m = 2 开始，它在守卫内调用 ndnp (m-1) = ndnp 1，从而导致无限循环。

您可以通过重命名列表理解中新引入的迭代变量来解决该问题:

ndnp n = [n' | n' <- (ndnp (n-1)), mod n' (head $ ndnp (n-1)) /= 0]

观察替换 n = 1 得出:

ndnp 1 = [n' | n' <- ndnp 0, mod n' (head $ ndnp 0) /= 0]

然后替换 ndnp 0 = nums0 得出:

ndnp 1 = [n' | n' <- nums0, mod n' (head nums0) /= 0]

它与您对 nums1 的定义完全匹配，直至变量替换。

因此，此示例中没有违反引用透明度。

您发现的修复:

ndnp n = [n | n <- arr, mod n (head $ arr) /= 0]
     where arr = ndnp (n-1)

的范围不同。 Haskell 作用域规则意味着它相当于:

ndnp n = [m | m <- arr, mod m (head $ arr) /= 0]
          ^   ^             ^
     where arr = ndnp (n-1)

看看新变量 m 如何捕获列表推导式中每次出现的 m，但不捕获 n 在arr 的定义中？这意味着这相当于:

ndnp n = [m | m <- ndnp (n-1), mod m (head $ ndnp (n-1)) /= 0]
          ^   ^                    ^

其中 ndnp (n-1) 都没有被捕获，使其相当于我上面的“固定”版本，直到变量重命名:

ndnp n = [n' | n' <- (ndnp (n-1)), mod n' (head $ ndnp (n-1)) /= 0]
          ^^   ^^                      ^^