我的意思是,从定义来看:
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
的编码递归提供一个实际的、实用的答案。