2

我的意思是,从定义来看:

fix f是函数的最小不动点f

换句话说:

最小的定义x使得f x = x.

任何空值类型的最少定义值是undefined。这里仍然存在一些歧义,undefined可能意味着“将引发错误”(更好)或“永远不会终止”(更糟)。正如推理和试验所表明的那样,fix (+1)两者fix pred :: Word似乎都从未接近终止(即使pred 0是一个错误),所以“永不终止”中最糟糕的一个很可能总是在这两种选择之间被选择。(能逃脱fix的就是无聊const 1,以后再说吧。)

这不是有用的申请方式fix

有用的应用方式fix是:

fix (\f x -> if x > 7 then f (x - 1) else x)

-- 即使用fix来神奇地产生一个递归函数。(这总是让我感到惊讶。)这可以被视为在 2 个函数之间进行选择:\f x -> f (x - 1)\_ x -> x,其中一个永远不会评估其第一个绑定变量。这是一个危险的玩具,因为我们仍然可以很容易地获得一个在其一半域内不终止的函数,就像意外翻转><-to一样容易+

所以,不知何故,这两个功能:

f1 = \f x -> f (x - 1)

f2 = \_ x -> x

-- 后者是“最少定义的”。如果我们用力眯起眼睛,我们实际上可以认出我们无聊的家伙const,只是flip'd。

现在,这是违反直觉的。f2实际上更具容错性,因此从某种意义上说,它被定义为f1. (特别是,这是让它逃脱否则无限循环的原因fix)。具体来说,f2为所有相同(f, x)的输入对定义为f1加上(undefined, x). 同样,const 1是所有一元函数中容错能力最强的。

那么,我现在如何理解定义性


这个问题的一些理由

附近有这个答案fix,它提供了与这个问题中提出的不同的直觉。它还强调,为了全面理解,必须通过关于指称语义的外部教程。

我想得到一个答案,要么支持,要么解释这里提出的直觉的错误,而且,如果领域理论真的是评论中提出的草书顺序的背后,至少包括一些经验法则,允许,不管多么有限,但领域理论的实际应用。我希望看到的问题的一个特定部分是一个有fix能力的函数是否总是可以分解为一个常量函数和一个归约函数,以及这些函数类的定义是什么。

我的愿望是在可靠的数学推理的支持下,就构建有用且安全fix的编码递归提供一个实际的、实用的答案。

4

1 回答 1

6
于 2018-02-10T07:02:07.247 回答