我如何使用修复,如何工作?
-
24-10-2019 - |
题
我对文档有点困惑 fix
(尽管我认为我知道现在应该做什么),所以我查看了源代码。那使我更加困惑:
fix :: (a -> a) -> a
fix f = let x = f x in x
这如何返回固定点?
我决定在命令行中尝试一下:
Prelude Data.Function> fix id
...
它挂在那里。现在公平地说,这是我的旧MacBook上,这有点慢。但是,此功能不能是 也 计算上的昂贵,因为任何传递给ID的东西都可以使同一件事返回(更不用说它不吃CPU时间了)。我究竟做错了什么?
解决方案
你没错。 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 = 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所示的无限列表之类的事情。
汤姆德的阶乘解释很好。 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
模式可以匹配并终止吗?好吧,这不是完全正确的。汤姆德说明了我们如何扩展 x
应用功能并迈向基本情况。为了他的功能,他使用了一个if/then,这就是导致终止的原因。重复替换后, in
整个定义的一部分 fix
最终停止根据 x
那就是它可以计算和完整的。
您需要一种方法才能终止固定点。扩展您的示例很明显它不会完成:
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
如果您仍然感到困惑,那么也许阶乘将是一个简单的例子:
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,Undefined和Infinite Loops中的无限环路)或其中最不确定的循环。例如,使用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
, ,没有无限的环路或未定义的循环。