我如何使用修复，它是如何工作的? [英] How do I use fix, and how does it work?

问题描述

我对 fix 的文档有点困惑(虽然我想我现在明白它应该做什么)，所以我查看了源代码.这让我更加困惑:

I was a bit confused by the documentation for fix (although I think I understand what it's supposed to do now), so I looked at the source code. That left me more confused:

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

这究竟如何返回一个固定点?

How exactly does this return a fixed point?

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

I decided to try it out at the command line:

Prelude Data.Function> fix id
...

它就挂在那里.公平地说，这是在我的旧 macbook 上，有点慢.然而，这个函数在计算上不能太，因为任何传递给 id 的东西都会返回同样的东西(更不用说它没有占用 CPU 时间).我做错了什么?

And it hangs there. Now to be fair, this is on my old macbook which is kind of slow. However, this function can't be too computationally expensive since anything passed in to id gives that same thing back (not to mention that it's eating up no CPU time). What am I doing wrong?

推荐答案

你没有做错任何事.fix id 是一个无限循环.

You are doing nothing wrong. fix id is an infinite loop.

当我们说 fix 返回函数的最小不动点时，我们的意思是在 领域理论 意义.所以fix (x -> 2*x-1) 不会返回1，因为虽然1code> 是该函数的一个不动点，它不是域排序中的最少.

When we say that fix returns the least fixed point of a function, we mean that in the domain theory sense. So fix (x -> 2*x-1) is not going to return 1, because although 1 is a fixed point of that function, it is not the least one in the domain ordering.

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

I can't describe the domain ordering in a mere paragraph or two, so I will refer you to the domain theory link above. It is an excellent tutorial, easy to read, and quite enlightening. I highly recommend it.

对于 10,000 英尺的视图，fix 是一个高阶函数，它编码了递归的思想.如果你有表达式:

For the view from 10,000 feet, fix is a higher-order function which encodes the idea of recursion. If you have the expression:

let x = 1:x in x

结果是无限列表 [1,1..]，你可以使用 fix 说同样的话:

Which results in the infinite list [1,1..], you could say the same thing using fix:

fix (x -> 1:x)

(或者简单的fix (1:))，它说给我找到(1:)函数的一个不动点，IOW一个值x 使得 x = 1:x... 就像我们上面定义的那样.从定义中可以看出，fix无非就是这个想法——将递归封装成一个函数.

(Or simply fix (1:)), which says find me a fixed point of the (1:) function, IOW a value x such that x = 1:x... just like we defined above. As you can see from the definition, fix is nothing more than this idea -- recursion encapsulated into a function.

这也是递归的真正通用概念——您可以通过这种方式编写任何递归函数，包括使用多态递归的函数.例如典型的斐波那契函数:

It is a truly general concept of recursion as well -- you can write any recursive function this way, including functions that use polymorphic recursion. So for example the typical fibonacci function:

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

可以用fix这样写:

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

练习:展开fix的定义，说明fib的这两个定义是等价的.

Exercise: expand the definition of fix to show that these two definitions of fib are equivalent.

但要全面了解，请阅读领域理论.真是好东西.

But for a full understanding, read about domain theory. It's really cool stuff.

这篇关于我如何使用修复，它是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！