函数式编程中的纯函数都是连续的吗？

Question

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

Answer 1

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

不连续函数的一个例子是(pseudo-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 (() : () : _|_)
...

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

连续函数不一定是可计算的。例如任何 order-preserving（即 f _|_ = _|_ 或 f 是常量）函数 Integer -> Bool 是连续的，因为 Integer 是平面域。但当然只有可数的许多是可计算的。

函数式编程中的纯函数都是连续的吗？

Are all pure functions in functional programming continuous?

math

haskell

functional-programming

function

purely-functional