我如何使用修复程序，以及它如何工作？ [英] How do I use fix, and how does it work?

问题描述

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

  fix ::（a  - > a） - > a 
修复f = let x = fx in x 
  

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

我决定在命令行尝试它：

  Prelude Data.Function>修复ID 
 ... 
  

它在那里挂起。现在公平地说，这是我的旧的macbook，这是缓慢的。然而，这个函数的计算花费也不是很大，因为传入id的任何东西都会返回相同的结果（更不用说它没有CPU时间了）。我做错了什么？

解决方案

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

当我们说 fix 返回函数的最小固定点，我们的意思是在领域理论感。因此，修复（\ x - > 2 * x-1）不会返回 1 ，因为虽然 1 是该函数的一个固定点，但它不是域中排序中的至少。

我无法用一两个段落来描述域的排序，所以我会参考上面的域理论链接。这是一个很好的教程，易于阅读，颇具启发性。我强烈推荐它。

对于10,000英尺的视图， fix 是一个高阶函数，它编码递归的想法。如果您有以下表达式：

  let x = 1：x in x 
  

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

 修复（\ x  - > 1： x）
  

（或简单地 fix（1：）），它表示找到（1：）函数的一个固定点，IOW一个值 x x = 1：x ...就像我们上面定义的那样。从定义中可以看出， fix 不过是这个想法 - 将递归封装到一个函数中。

它也是递归的一个真正的一般概念 - 你可以用这种方式编写任何递归函数，包括使用多态递归的函数。例如，典型的斐波那契函数：

  fib n = if if n < 2 then n else fib（n-1）+ fib（n-2）
  

可以使用 fix 这样：

  fib = fix（\f  - > ;如果n <2则n等于f（n-1）+ f（n-2））
  

练习：展开 fix 的定义，以显示 fib 的这两个定义是相当于。

但是要充分理解，请阅读域理论。这真的很酷。

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
...

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?

解决方案

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

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.

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

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

fix (\x -> 1:x)

(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)

Can be written using fix this way:

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

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屋！