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

Question

我对文档感到有些困惑fix(虽然我认为我理解它现在应该做什么),所以我查看了源代码.这让我更加困惑:

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

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

我决定在命令行试一试:

Prelude Data.Function> fix id
...

它挂在那里.现在公平地说,这是在我的旧Macbook上,这有点慢.但是,此功能也不能太过,因为任何东西传递给ID给出了同样的事情,回(更不用提,它的吃了没有CPU时间)计算昂贵.我究竟做错了什么？

Answer 1

你没有做错任何事. 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:)功能,督察的值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是等价的.

但为了充分理解,请阅读有关领域理论的内容.这真的很酷.

Answer 2

我根本不会理解这一点,但如果这有助于任何人...那么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)a -> a(b -> b) -> (b -> b)ab -> b

等等,我以为它应该返回一个固定的点...而不是一个函数.它确实如此(因为函数是数据).你可以想象它给了我们找到阶乘的决定性功能.我们给了它一个不知道如何递归的函数(因此其中一个参数是一个用于递归的函数),并fix教会它如何递归.

还记得我说过f必须生成某种结构,以便以后f可以模式匹配和终止吗？嗯,这不完全正确,我想.TomMD说明了我们如何扩展x以应用函数并逐步实现基本情况.对于他的功能,他使用了if/then,这就是导致终止的原因.在重复替换之后,in整个定义的一部分fix最终停止被定义为,x并且在可计算和完成时.

Answer 3

您需要一种方法让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 -->

我会在这里停下来!