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

Question

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

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它是一个平面域。但当然，其中只有可数的许多是可计算的。