哈斯克尔的"fix"是什么?为什么"fix error"打印无限字符串?为什么"take 10 $ fix error"也这样做呢?



长话短说,我当时正在看西蒙·佩顿·琼斯的讲座,在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 errorlength $ take 10 $ fix error也会给出如上所述的永无止境的输出(除了后者的输出length …缺少初始")。

我在看什么?


需要明确的是,目前我还不太了解关于黑客的文档。我仍然迷失在它的第一行。

fix计算函数的不动点;不动点是一个可以输入到函数的值,它将产生与结果完全相同的值。

例如,如果您有函数f _ = "hello"(或const "hello"),那么该函数的一个不动点就是字符串"hello"。实际上fix f就是"hello"

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

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

每个偶数都是g的不动点,但fix g(按其类型)承诺是特定的Integer。哪一个?

该文档称fix产生最小不动点,并进一步阐明这意味着定义最少的值是输入函数的不动点。注意,";定义最少的";不是指所定义的最小值;定义性";。这是一个我不太了解的技术领域,但我至少可以给你一些非正式的直觉,让你了解它的含义11 :: IntegerTrue()Just 'a'等值是完全定义的,因为你可以在不出错的情况下对它们进行全面评估。底部值(undefinedlet 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为什么会这样。范昂森的回答很好,所以我不再赘述。但基本上fix error必须想出一个字符串s,使得error s等价于s。当然,这对于任何非底部字符串来说都是不可能的,因为error总是产生底部(这就是它的全部意义),所以fix error必须是某种形式的底部。在搜索不动点时,它会生成一个无限嵌套的表达式error (error (error ...)),当GHC打印一条错误消息时,它本身会生成一条消息是另一个错误的错误,等等,你看到的是生成的输出。


1;定义最少的";来自领域理论。如果你想了解更多,评论中建议了几个链接:

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

它产生error (error (error (error …)))。由于error的类型为[Char] -> a,我们知道这里是a ~ [Char],所以error (error (error (error …)))的类型将为[Char]。一旦我们对此进行评估,它将引发一个错误,因此它打印*** Exception:,然后旨在打印消息,但这也是一个error,所以它打印另一个*** Exception:,依此类推

为什么take 10 $ fix error也这么做?

因为当它的目标是获取列表的前10个元素时也会出错,因为评估列表会引发错误,而当打印异常时,同样的行为也会开始。

因此,它从不生成Char的列表:它引发错误并开始打印错误消息,而不是返回

考虑它的一个简单方法是,您可以使用它将嵌套表达式本身作为参数,使其递归。例如,在这里,我用它来制作一个允许数字插入嵌套的解析器:

ghci> :m + Data.Function Text.Parsec
ghci> parseTest (fix $  nestedDigit -> digit <|> char '(' *> nestedDigit <* char ')') "((3))"
'3'

您可以将其视为常规递归绑定的替代方案:

ghci> let
ghci| nestedDigit :: Parsec String () Char
ghci| nestedDigit = digit <|> char '(' *> nestedDigit <* char ')'
ghci|
ghci> parseTest nestedDigit "((3))"
'3'

如果您想在表达式递归时将其保留在使用位置,这有助于避免编写模式(let foo = ... foo ... in foo)

正如本的回答所示,它还有更多的用途,但在实践中,我还没有找到除此之外的其他好用途。

相关内容

最新更新