我如何使用修复程序，它是如何工作的？

我对fix的文档感到有点困惑（虽然我想我明白它应该做什么），所以我查看了源代码。这让我更加困惑：

fix :: (a -> a) -> a
fix f = let x = f x in x

这究竟是如何返回固定点的？我决定在命令行试一试：

Prelude Data.Function> fix id
...

它挂在那里。现在公平地说，这是在我的旧Macbook上，这有点慢。但是，这个函数的计算成本太高，因为传入id的任何内容都会返回同样的东西（更不用说它不占用CPU时间）。我究竟做错了什么？

已邀请:

5 个回复

宦哨抹存胳

你没有做错任何事。 fix id是一个无限循环。当我们说fix返回函数的最小固定点时，我们的意思是在域论意义上。所以fix (x -> 2*x-1)不会返回1，因为虽然1是该函数的一个固定点，但它并不是域排序中的最小值。我无法在一两段内描述域名排序，因此我将向您推荐上面的域名理论链接。这是一个很好的教程，易于阅读，而且非常有启发性。我强烈推荐它。对于10,000英尺的视图，fix是一个高阶函数，它编码递归的概念。如果您有表达式：

let x = 1:x in x

这导致无限列表[1,1..]，你可以用fix说同样的事情：

fix (x -> 1:x)

（或简单地说是fix (1:)），它说找到了(1:)函数的一个固定点，Iow值为x，使得x = 1:x......就像我们上面定义的那样。从定义中可以看出，fix只不过是这个想法 - 递归封装到一个函数中。它也是一个真正普遍的递归概念 - 你可以用这种方式编写任何递归函数，包括使用多态递归的函数。例如，典型的斐波那契函数：

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

可以这样使用fix编写：

fib = fix (f -> n -> if n < 2 then n else f (n-1) + f (n-2))

练习：扩展fix的定义，表明fib的这两个定义是等价的。但为了充分理解，请阅读有关领域理论的内容。这真的很酷。

搜洼挂时

我根本不会理解这一点，但如果这有助于任何人...那么yippee。考虑fix的定义。 fix f = let x = f x in x。令人难以置信的部分是x被定义为f x。但想一想。

x = f x

由于x = f x，那么我们可以用右边的x的值代替，对吧？因此......

x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.

所以诀窍是，为了终止，f必须生成某种结构，以便后来的f可以模式匹配该结构并终止递归，而不实际关注其参数的完整“值”（？）当然，除非你想做一些像创建无限列表的东西，如luqui所示。 TomMD的因子解释很好。 Fix的类型签名是(a -> a) -> a。 (recurse d -> if d > 0 then d * (recurse (d-1)) else 1)的类型签名是(b -> b) -> b -> b，换句话说，(b -> b) -> (b -> b)。所以我们可以说a = (b -> b)。这样，修复需要我们的功能，即a -> a，或者真的，(b -> b) -> (b -> b)，并将返回类型a的结果，换句话说，b -> b，换句话说，另一个函数！等等，我以为它应该返回一个固定的点...而不是一个函数。它确实如此（因为函数是数据）。你可以想象它给了我们找到阶乘的决定性功能。我们给了它一个不知道如何递归的函数（因此其中一个参数是一个用于递归的函数），并且fix教它如何递归。还记得我怎么说f必须产生某种结构，以便后来的f可以模式匹配并终止？嗯，这不完全正确，我想。 TomMD说明了我们如何扩展x以应用功能和步骤基础案例。对于他的功能，他使用了if / then，这就是导致终止的原因。经过反复更换后，fix整个定义的in部分最终不再以x定义，即可计算和完成时。

吞睫素

您需要一种方法让fixpoint终止。扩展你的例子很明显它不会完成：

fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...

这是我使用修复程序的一个真实示例（注意我不经常使用修复程序，可能很累/在编写此代码时不担心可读代码）：

(fix (f h -> if (pred h) then f (mutate h) else h)) q

WTF，你说！嗯，是的，但这里有一些非常有用的要点。首先，你的第一个fix参数通常应该是一个“递归”情况的函数，第二个参数是要作用的数据。这是与命名函数相同的代码：

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

如果你仍然感到困惑，那么也许factorial将是一个更简单的例子：

fix (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

注意评估：

fix (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (d -> if d > 0 then d * (x (d-1)) else 1) 3

哦，你刚才看到了吗？那x成为我们then分支内部的一个功能。

let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->

在上面你需要记住x = f x，因此最后两个参数x 2而不仅仅是2。

let x = ... in 3 * (d -> if d > 0 then d * (x (d-1)) else 1) 2 -->

我会在这里停下来！

臀夯脖锑

一个明确的定义是你也可以重新发明修复！

嗓瑰

我的理解是，它为函数找到了一个值，这样它就会输出你给它的东西。问题是，它将始终选择未定义（或无限循环，在haskell中，未定义和无限循环是相同的）或其中包含最多未定义的内容。例如，有了id，

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

如你所见，undefined是一个固定点，所以fix会选择它。如果你改为（ x-> 1：x）。

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (x->1:x) undefined
[1*** Exception: Prelude.undefined

所以fix不能选择undefined。使它更多地连接到无限循环。

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (x->1:x) (let y=y in y)
[1^CInterrupted.

再次，略有不同。那么固定点是什么？让我们试试repeat 1。

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

这是相同的！由于这是唯一的固定点，fix必须解决它。对不起fix，没有无限循环或未定义。

要回复问题请先登录或注册

我如何使用修复程序，它是如何工作的？

5 个回复

发起人

y_combinator

letrec

问题状态

我如何使用修复程序，它是如何工作的？

与内容相关的链接

5 个回复

发起人

y_combinator

letrec

问题状态