Haskell中的定点组合器 [英] Fixed point combinator in Haskell

问题描述

 修复f = f（修复f ）
  

以下代码不会终止：

 修复（\ x-> x * x）0 
  

当然， fix 并不总能产生正确的答案，但我想知道，这可以改进吗？

当然，对于上面的例子，可以实现一些看起来像

 修复fx | f x == f（f x）= f x 
 |否则=修正f（fx）
  

并给出正确的输出。

上面定义的原因是什么（或者更好，因为这个只能处理带有1个参数的函数）不被用来代替？

解决方案

固定点组合器找到函数的最小定义的固定点，在您的情况下为⊥（非终止的确是未定义的值）。

您可以检查，在您的情况下

 （\ x  - > x * x）⊥= ⊥
  

即⊥确实是 \x - >的固定点。 x * x 。

至于为什么定义 fix ：main点修复可让您使用匿名递归和因为你不需要更复杂的定义。

The fixed point combinator doesn't always produce the right answer given the definition:

fix f = f (fix f)

The following code does not terminate:

fix (\x->x*x) 0

Of course, fix can't always produce the right answer, but I was wondering, can this be improved?

Certainly for the above example, one can implement some fix that looks like

fix f x | f x == f (f x)  = f x
        | otherwise       = fix f (f x)

and gives the correct output.

What is the reason the above definition (or something even better, as this one only handle function with 1 parameter) is not used instead?

解决方案

Fixed point combinator finds the least-defined fixed point of a function, which is ⊥ in your case (non-termination indeed is undefined value).

You can check, that in your case

(\x -> x * x) ⊥ = ⊥

i.e. ⊥ really is fixed point of \x -> x * x.

As for why is fix defined that way: the main point of fix is to allow you use anonymous recursion and for that you do not need more sophisticated definition.

这篇关于Haskell中的定点组合器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！