Czy funkcje wyższego rzędu zapewniają większą moc programowaniu funkcjonalnemu?

Zadałem podobne pytanie na cstheory.SE .

Zgodnie z tą odpowiedzią na Stackoverflow istnieje algorytm, który w nieliniowym czystym funkcjonalnym języku programowania ma złożoność , podczas gdy tym samym algorytmem w programowaniu imperatywnym jest Ω ( n ) . Dodanie lenistwa do języka FP spowodowałoby, że algorytm Ω ( n ) .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

Czy istnieje równoważna relacja porównująca język FP z funkcjami wyższego rzędu i bez nich? Czy to wciąż Turing Complete? Jeśli tak, to czy brak wyższego porządku w FP sprawia, że ​​język jest mniej „mocny” lub wydajny?

W funkcjonalnym języku programowania, który jest wystarczająco wydajny (na przykład z typami danych do implementacji zamknięć ), można wyeliminować wszystkie zastosowania wyższego rzędu poprzez transformację defunkcjonalizacji . Ponieważ ta metoda jest używana do kompilacji tego rodzaju języka, można zasadnie założyć, że nie wpływa to na wydajność i że w tym ustawieniu wyższa kolejność nie zmniejsza mocy języka. Wpływa to jednak na sposób pisania kodu.

Jeśli jednak język nie jest wystarczająco mocny, to tak, wyższy porządek zapewnia moc ekspresji. Rozważ rachunek lambda: bez żadnej funkcji wyższego rzędu naprawdę nie może nic zrobić, głównie dlatego, że najbardziej podstawowe typy danych (liczby całkowite, logiczne) są implementowane za pomocą funkcji.

Podsumowując, to naprawdę zależy od języka.

---

Powyżej jest moja odpowiedź. Poniżej komentarz na temat zwykłego założenia dotyczącego języków imperatywnych.

$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

$n$$O(1)$$O(\log n)$$O(\log m)$$m$$m≥n$$m$$n$

$O(1)$

To zależy od tego, co rozumiesz przez ekspresję.

Oto argument, że wyższy porządek coś dodaje: w językach pierwszego rzędu rekurencja pierwotna nie wystarcza do wyrażenia funkcji Ackermanna . Jednak w obecności funkcji wyższego rzędu wystarczy prymitywna rekurencja:

$$\begin{array}{lcl} \textit{Ackermann} \ 0 & = & \lambda x. x+1 \\ \textit{Ackermann} \ ( m+1 ) & = & \textit{Iter}\ ( \textit{Ackermann}\ m ) \\ \textit{Iter}\ f\ 0 & = & f\ 1 \\ \textit{Iter}\ f\ ( n+1 ) & = & f\ ( \textit{Iter}\ f\ n ) \end{array}$$

Definiuje to funkcję Ackermanna przy użyciu tylko pierwotnej rekurencji.

$\textit{Iter}$$\textit{Iter}$$\mathbb{N}^k \rightarrow \mathbb{N}$$k$$\textit{Iter}$$(\mathbb{N} \rightarrow \mathbb{N}) \rightarrow (\mathbb{N} \rightarrow \mathbb{N})$