Haskell中的引用透明度混淆

ccrfmcuu 于 2023-08-06 发布在其他

关注(0)|答案(1)|浏览(99)

首先，尽管这是埃拉托塞尼筛子的一个实现，但这不是一个家庭作业问题。我可以在许多介绍书中找到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函数，该函数返回不能被第一个m素数整除的大于1的自然数列表，即

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)

型
这使我的代码工作，但没有给予我一个很好的概念性理解，当我有引用透明性，当我没有。

haskell

来源：https://stackoverflow.com/questions/76808459/referential-transparency-confusion-in-haskell

1条答案

按热度按时间

67up9zun1#

如果你打开了警告（这是一个很好的实践-这对我来说有点神秘，很多编译器，包括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的新定义 * 并没有 * 捕获第一次出现ndnp (n-1)时的n，但它捕获了解析中的所有其他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的每次出现，但 * 不 * 捕获arr定义中的n了吗？这意味着这相当于：

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]
          ^^   ^^                      ^^

型

赞(0）回复(0）举报 2023-08-06

我来回答

Haskell中的引用透明度混淆

1条答案

相关问题

热门标签

最新问答