Fonksiyonel programlamanın tüm saf fonksiyonları sürekli mi?

Question

Haskell işlev kümesinin tüm matematiksel işlevlerin yalnızca bir alt kümesi olduğunu biliyorum, çünkü bu bir programlama dilidir, bu nedenle tüm işlevleri hesaplanabilir olmalıdır. Ancak tüm Haskell fonksiyonlarının (ve genel olarak saf fonksiyonların) matematiksel açıdan continuous olduğu doğru mu?

Answer 1

Bağlantılı olduğunuz Wikipedia sayfasının ikinci paragrafında belirtilen Scott sürekliliği açısından hesaplanabilir işlevler süreklidir.

(psödo-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 : _|_ -} = _|_ 

Bu

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

dizisi

arasında sup olduğu için sürekli olmak başarısız değildir sürekli olduğu bir fonksiyonun örneği,

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

ama

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

sonlu bir zaman miktarında bir fonksiyonu sadece girdinin bir sınırlı miktarda incelemek dolayı özel,

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

Hesaplanabilir fonksiyonlar süreklidir dizisinin sup değildir. Dolayısıyla, eğer hesaplanabilir bir işlev, belirli bir girişte True döndürürse, belirli sonlu bir gözlemler koleksiyonu üzerindeki orijinal girdiyle aynı olan giriş kümesindeki her girişe True dönmelidir. Orijinal girdiye yakınlaşan herhangi bir artan dizi sonunda bu kümenin içine inecek ve bu dizide kalacak, böylece bu artan dizi üzerindeki fonksiyonun değerleri dizisi True'a yakın olacaktır.

Sürekli bir işlev zorunlu olarak hesaplanabilir değildir. Örneğin, Integer düz bir etki alanı olduğundan, herhangi bir sipariş koruyucu (yani f _|_ = _|_ veya f sabittir) işlevi Integer -> Bool süreklidir. Ancak elbette, sadece birçoğu kararlaştırılabilir.