Haskell 中的“修复”是什么？为什么“修复错误”会打印无限字符串？为什么“拿 10 美元修复错误”也有同样的作用？

Question

长话短说，我正在观看Simon Peyton-Jones 的演讲，当时21:41他引用了一段话：

\n

\n

我正在解决一个错误，感到沮丧，并在 ghci\xe2\x80\xa6 中输入“修复错误”

\n

\n

所以我尝试了。

\n

结果：

\n

\xce\xbb> import Data.Function -- here is fix\n\xce\xbb> fix error\n"*** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: *** Exception: and goes on like this towards infinity\n

\n

起初，我只是想“这到底是做什么用的？”fix做什么的？”

\n

所以我看了一些类型：

\n

\xce\xbb> :t error\nerror :: [Char] -> a\n\xce\xbb> :t fix\nfix :: (a -> a) -> a\n

\n

因此，

\n

\xce\xbb> :t fix error\nfix error :: [Char]\n

\n

但显然这仍然没有告诉我太多关于结果的信息。

\n

然而，对我来说最奇怪的是，甚至take 10 $ fix error或length $ take 10 $ fix error给出了像上面这样的永无休止的输出（除了后者的输出 ，length \xe2\x80\xa6缺少初始的"）。

\n

我在看什么？

\n

---

\n

需要明确的是，目前我对hackage 的文档仍然不太了解。我仍然迷失在它的第一行。

\n

Answer 1

fix计算函数的不动点；定点是一个可以提供给函数的值，函数将生成与结果完全相同的值。

例如，如果有函数f _ = "hello"(or const "hello")，那么该函数的不动点就是字符串"hello"。确实fix f是"hello"。

许多函数都有多个不动点，因此 的文档fix需要指定它返回哪一个。例如：

g :: Integer -> Integer
g x
  | even x = x
  | otherwise = x + 1

每个偶数都是 的固定点g，但fix g承诺（通过其类型）是特定的Integer。哪一个？

该文档说fix产生最小固定点，并进一步阐明这意味着作为输入函数固定点的最小定义值。请注意，“最少定义”并不意味着定义的最小值，而是意味着具有最小“定义度”的值。这是一个技术领域，我并不像我希望的那样精通，但我至少可以给你一些关于它的含义的非正式直觉¹1 :: Integer ：像、True、()等这样的值Just 'a'是完全定义的，因为你可以全面评估它们而不会出错。底部值（undefined、let x = x in x等）完全未定义。中间是类似的值1 : 2 : undefined，您可以在其中查看某些结构而不会遇到错误，但内部某个地方有一个底部。因此，如果底部是一种可能性，那么它始终是最不明确的可能性。

所以fix g就是底部（当我尝试时，GHC 检测到无限循环并中止它），因为g undefined是一个错误（为此目的，所有底部都是“相同的值”）。

事实证明，对于您在使用 时可能编写的大多数简单函数来说都是这种情况fix。对于任何严格函数（以任何方式检查其参数的函数），底部将是一个固定点，这就是fix要计算的点。因此，当您只是闲逛试图了解它的作用时，它可能看起来毫无用处。那么我们为什么要关心它呢？

fix具有很大的理论意义，因为您可以使用它以缺乏直接支持的语言来实现递归。在这样的递归定义中：

sum :: [Integer] -> Integer
sum [] = 0
sum (x : xs) = x + sum xs

实际上正在发生一些令人印象深刻的事情。您正在定义sum，但sum在其自己定义的范围内。实现该功能比编译仅使用预先存在的定义的定义要困难一些。假设我们无法做到这一点，但我们仍然想写sum。你可以这样做：

sum' :: ([Integer] -> Integer) -> [Integer] -> Integer
sum' _ [] = 0
sum' rec (x : xs) = x + rec xs

sum = fix sum'

现在每个定义都只使用之前定义过的东西；没有自我参考。不是直接调用自身而是sum'接收一个额外的参数，该参数是它应该在列表尾部调用的函数。该函数参数必须具有与我们最初想要给出的类型相同的类型sum，这使得类型成为 的sum'实例a -> a，以便我们可以调用fix它。事实证明 的最小不动点sum'是一个与原始 等价的函数sum！

它的方法是生成一个“无限嵌套”形式的表达式sum' (sum' (sum' (sum' ...)))（这基本上是它找到任何函数的不动点的方式；答案已经很长了，所以我不会详细说明为什么它会起作用这里）。每个人sum'都会收到一个参数，说明如何处理列表的尾部；该参数本身是对 的另一个调用，sum'需要一个参数来说明如何处理原始列表尾部的尾部，并且该参数是对 的另一个调用sum'，依此类推。最终（如果列表是有限的）我们达到空列表的基本情况，并且不需要下一级嵌套sum'调用，因此嵌套表达式没有结束并不重要！（显然，这在急切评估的语言中行不通）

事实证明，这是一种通用模式，您可以应用它来将直接递归转换为fix.

说了这么多，希望您能明白为什么fix error会这样。Willem Van Onsem 的回答很好，所以我不再详细重复。但基本上fix error必须想出一个s相当于 的error s字符串s。这对于任何非底部字符串来说当然是不可能的，因为error总是产生底部（这就是它的全部意义），所以fix error必须是某种形式的底部。在搜索固定点时，它会生成一个无限嵌套的表达式error (error (error ...))，并且当 GHC 打印一条错误消息时，该错误消息本身会生成一个错误，该错误的消息是另一个错误，等等，您所看到的是生成的输出。

¹ “最少定义”的概念来自领域理论。如果您想了解更多信息，评论中建议了几个链接：

• 领域理论初学者课程的讲义：https://www.cs.nott.ac.uk/~pszgmh/domains.html
• 关于 Haskell 中的指称语义的 Wikibooks 文章并不是专门关于领域理论，但确实比我更详细地讨论了这个特定的概念：https ://en.m.wikibooks.org/wiki/Haskell/Denotational_semantics

Answer 2

它产生error (error (error (error \xe2\x80\xa6))). 既然error有类型[Char] -> a，我们知道这里a ~ [Char]，所以就会error (error (error (error \xe2\x80\xa6)))有类型[Char]。一旦我们对此进行评估，它就会引发错误，因此它会打印，*** Exception: 然后旨在打印该消息，但这也是一个error，因此它会打印另一个*** Exception: ，依此类推。

\n

\n

为什么还take 10 $ fix error这样做呢？

\n

\n

因为当它打算获取列表的前 10 个元素时，它也会出错，因为评估列表会引发错误，并且在打印异常时，将开始相同的行为。

\n

因此，它永远不会生成 s 列表Char：它会引发错误并开始打印错误消息，而不返回它。

\n