6

Wiem, że zestaw funkcji Haskella jest tylko podzbiorem wszystkich funkcji matematycznych, ponieważ jest to język programowania, więc wszystkie jego funkcje muszą być obliczalne. Ale czy to prawda, że ​​wszystkie funkcje Haskella (i ogólnie funkcje czyste) są z matematycznego punktu widzenia continuous?Czy wszystkie czyste funkcje w programowaniu funkcjonalnym są ciągłe?

+1

@ HarryDeveloper1212 Myślę, że to dobre pytanie. Dokonałem pewnych poprawek, aby (mam nadzieję) wyjaśnić, co rozumiem przez to pytanie. Jeśli nie jesteś zadowolony z moich zmian, możesz ponownie [edytować swoje pytanie] (http://stackoverflow.com/posts/34617662/edit), aby je przywrócić. –

Odpowiedz

18

Funkcje obliczalne są ciągłe w sensie ciągłości Scotta, o których mowa w drugim akapicie strony Wikipedii, do której jesteś podłączony.

Przykładem funkcji, która jest nie stała jest (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 : _|_ -} = _|_ 

to nie w sposób ciągły, ponieważ

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

jest Supremum sekwencji

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

ale

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

nie supremum sekwencji

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

funkcje obliczalne są ciągłe, ponieważ w skończonym czasie funkcja może kontrolować tylko skończoną ilość jego wejścia. Jeśli więc funkcja obliczeniowa zwróci, powiedzmy, True na określonym wejściu, musi zwrócić True na każdym wejściu w zestawie wejść, które zgadzają się z pierwotnym wejściem w pewnym skończonym zbiorze obserwacji. Każda rosnąca sekwencja, która zbiega się z pierwotnym wejściem, ostatecznie wyląduje i pozostanie w tym zbiorze, więc sekwencja wartości funkcji w tej rosnącej sekwencji będzie zbieżała się z True.

Funkcja ciągła nie musi być obliczalna. Na przykład funkcja zachowywania porządku (tj. f _|_ = _|_ lub f jest stała) funkcja Integer -> Bool jest ciągła, ponieważ Integer jest domeną płaską. Ale oczywiście tylko niezliczona liczba z nich jest obliczalna.

+0

Doskonała, czysta odpowiedź. – luqui