Are all pure functions in functional programming continuous?

Question

I know that the set of Haskell functions is only a subset of all mathematical functions, because it is a programming language, so all of its functions must be computable. But is it true that all Haskell functions (and pure functions in general) are continuous, from a mathematical point of view?

Answer 1

Computable functions are continuous in the sense of Scott continuity, mentioned in the second paragraph of the Wikipedia page you linked to.

An example of a function which is not continuous is (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 : _|_ -} = _|_

It fails to be continuous because

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

is the supremum of the sequence

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

but

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

is not the supremum of the sequence

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

Computable functions are continuous, essentially because in a finite amount of time a function can only inspect a finite amount of its input. So if a computable function returns, say, True on a particular input, it must return True on every input in the set of inputs which agree with the original input on a certain finite collection of observations. Any increasing sequence which converges to the original input will eventually land and stay inside this set, so the sequence of values of the function on this increasing sequence will converge to True.

A continuous function is not necessarily computable. For example any order-preserving (i.e. f _|_ = _|_, or f is constant) function Integer -> Bool is continuous, since Integer is a flat domain. But of course only countably many of them are computable.