什么是Haskell中的“修复”？为什么“修复错误”打印无限字符串？为什么“取10美元修复错误”也是如此？

Question

长话短说，我在看西蒙·佩顿·琼斯的演讲，在21:41的时候，他引用了一句话：

我当时正在处理一个bug，很沮丧，在ghci中输入了“修复错误”…

我试过了。

结果：

λ> import Data.Function -- here is fix
λ> fix error
"*** 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

一开始我只是想，这个fix到底做了什么？

所以我看了一些类型

λ> :t error
error :: [Char] -> a
λ> :t fix
fix :: (a -> a) -> a

因此

λ> :t fix error
fix error :: [Char]

但很明显，这仍然没有告诉我多少结果。

然而，更奇怪的是，即使是take 10$fix error或length$take 10$fix error的输出也和上面的一样是一个永不间断的输出（除了后者的输出，length…，缺少首字母“）。

我在看什么？

需要明确的是，目前我仍然不太了解关于黑客的文档。并不是说我花了超过3分钟的时间，但我仍然迷失在第一行。

Answer 1

它会产生错误（error（error（error…））。因为错误的类型为[Char]-

为什么也拿10$修复错误也一样？

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

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

Answer 2

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

例如，如果您有函数f_="hello"（或const"hello"），则此函数的固定点是字符串"hello"。事实上修复f是"hello"。

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

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

每个偶数都是g的固定点，但fix gpromise（按其类型）是一个特定的整数。哪一个？

文档中说，fix产生的固定点最少，并进一步阐明，这意味着输入函数的固定点定义的值最少。请注意，“最小定义”并不是指定义的最小值，而是指具有最小“定义性”的值。在非正式意义上，这是一个技术领域，我并没有像我希望的那样处于最顶端：像1:：Integer，True，（，只是'a'等完全定义的值，因为您可以在不出错的情况下对它们进行全面评估。底部值（未定义，让x=x在x中等）完全未定义。中间是像1:2:undefined这样的值，在这些值中，您可以查看某些结构，而不会遇到错误，但内部某处有一个底部。

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

事实证明，在使用fix时编写的大多数简单函数都是如此。对于任何严格函数（以任何方式检查其参数的函数），bottom将是一个不动点，这就是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的一个实例-

它这样做的方式是通过生成形式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打印错误消息时，它本身会生成一个错误，而该错误消息是另一个错误，等等，您看到的是生成的输出。