98

我对文档有点困惑fix（尽管我想我现在明白它应该做什么），所以我查看了源代码。这让我更加困惑：

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

这究竟是如何返回一个固定点的？

我决定在命令行尝试一下：

Prelude Data.Function> fix id
...

它挂在那里。现在公平地说，这是在我的旧 macbook 上，有点慢。然而，这个函数在计算上不能太昂贵，因为任何传入 id 的东西都会返回相同的东西（更不用说它不会占用 CPU 时间）。我究竟做错了什么？

4

4 回答 4

100

你没有做错什么。 fix id是一个无限循环。

当我们说fix返回函数的最小不动点时，我们的意思是在域理论意义上。所以fix (\x -> 2*x-1)不会return ，因为虽然它是该函数的一个不动点，但它不是域排序中最不重要的一个。11

我无法仅用一两段来描述域排序，因此我将向您推荐上面的域理论链接。这是一个很好的教程，易于阅读，而且很有启发性。我强烈推荐它。

对于 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是等价的。

但要全面了解，请阅读领域理论。这真是很酷的东西。

于 2011-01-24T21:49:19.897 回答
27

我根本不声称自己理解这一点，但如果这对任何人都有帮助……那么 yippee。

考虑 的定义fix。fix f = let x = f x in x. 令人难以置信的部分是x定义为f x。但是想一想。

x = f x

既然 x = fx，那么我们可以代入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)。这样， fix 接受我们的函数，即a -> a，或真的，，(b -> b) -> (b -> b)并将返回类型的结果，a换句话说，b -> b，换句话说，另一个函数！

等等，我以为它应该返回一个固定点……而不是一个函数。不错，有点（因为函数是数据）。您可以想象它为我们提供了寻找阶乘的明确功能。我们给了它一个不知道如何递归的函数（因此它的一个参数是一个用于递归的函数），并fix教它如何递归。

还记得我说过f必须生成某种结构以便以后f可以模式匹配和终止吗？好吧，我猜这并不完全正确。TomMD 说明了我们如何扩展x以应用该功能并迈向基本案例。对于他的功能，他使用了 if/then，这就是导致终止的原因。经过反复替换，in整个定义的部分fix最终不再被定义x为可计算且完整的部分。

于 2011-01-25T02:17:33.160 回答
18

您需要一种方法来终止固定点。扩展您的示例很明显它不会完成：

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

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

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

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

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

如果您仍然感到困惑，那么阶乘可能是一个更简单的示例：

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而不是 just 2。

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

我会停在这里！

于 2011-01-24T22:00:59.083 回答
3

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

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

如您所见，未定义是一个固定点，因此fix将选择它。如果你改为 (\x->1:x)。

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

所以fix不能选择未定义的。使其与无限循环的联系更加紧密。

λ <*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，您没有无限循环或未定义。

于 2014-03-15T00:39:45.960 回答