function - 函数式编程中的所有纯函数都是连续的吗？

Question

我知道 Haskell 函数集只是所有数学函数的一个子集，因为它是一种编程语言，所以它的所有函数都必须是可计算的。但是，所有 Haskell 函数(以及一般的纯函数)都是 continuous 是真的吗？ ，从数学的角度来看？

Answer 1

可计算函数在斯科特连续性的意义上是连续的，在您链接到的维基百科页面的第二段中提到。

不连续函数的一个例子是(伪Haskell)

isInfinite :: [a] -> Bool
isInfinite xs
    | {- xs is an infinite list x0 : x1 : x2 : ... -}        = True
    | {- xs is a finite list x0 : x1 : x2 : ... : xn : [] -} = False
    | {- xs is a list with diverging spine
                            x0 : x1 : x2 : ... : xn : _|_ -} = _|_

它不能是连续的，因为

() : () : () : ...

是序列的上确界

_|_
() : _|_
() : () : _|_
...

但

True = isInfinite (() : () : () : ...)

不是序列的上确界

_|_ = isInfinite (_|_)
_|_ = isInfinite (() : _|_)
_|_ = isInfinite (() : () : _|_)
...

可计算函数是连续的，本质上是因为在有限的时间内，函数只能检查有限量的输入。因此，如果一个可计算函数返回，比如说， True在特定输入上，它必须返回 True在输入集合中的每个输入上，这些输入与某个有限观察集合上的原始输入一致。任何收敛到原始输入的递增序列最终都会落在这个集合内，所以这个递增序列上的函数值序列将收敛到 True .

连续函数不一定是可计算的。例如，任何保持顺序(即 f _|_ = _|_ 或 f 是常量)函数 Integer -> Bool是连续的，因为 Integer是一个平面域。但当然，其中只有可数的许多是可计算的。