Apakah Fungsi Tingkat Tinggi menyediakan lebih banyak daya untuk Pemrograman Fungsional?

Saya telah mengajukan pertanyaan serupa di cstheory.SE .

Menurut jawaban ini pada Stackoverflow ada algoritma yang pada bahasa pemrograman fungsional murni non-malas memiliki kompleksitas , sedangkan algoritma yang sama dalam pemrograman imperatif adalah Ω ( n ) . Menambahkan kemalasan ke bahasa FP akan membuat algoritma Ω ( n ) .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

Apakah ada hubungan setara yang membandingkan bahasa FP dengan dan tanpa Fungsi Pesanan Tinggi? Apakah masih Turing Lengkap? Jika ya, apakah kurangnya Orde Tinggi pada FP membuat bahasa kurang "kuat" atau efisien?

Dalam bahasa pemrograman fungsional yang cukup kuat (misalnya, dengan tipe data untuk menerapkan penutupan ) Anda dapat menghilangkan semua penggunaan urutan yang lebih tinggi dengan transformasi defungsionalisasi . Karena metode ini digunakan untuk mengkompilasi jenis bahasa ini, Anda dapat beranggapan bahwa ini tidak memengaruhi kinerja dan bahwa dalam pengaturan ini, tatanan yang lebih tinggi tidak membuat bahasa menjadi kurang kuat. Namun itu tidak mempengaruhi cara menulis kode.

Namun jika bahasanya tidak cukup kuat, maka ya, tatanan yang lebih tinggi memang memberikan kekuatan ekspresif. Pertimbangkan kalkulus lambda: tanpa fungsi tingkat tinggi, ia benar-benar tidak dapat melakukan apa pun, sebagian besar karena tipe data paling dasar (integer, boolean) diimplementasikan menggunakan fungsi.

Kesimpulannya, itu sangat tergantung pada bahasa.

---

Di atas adalah jawaban saya. Di bawah, komentar tentang asumsi umum tentang bahasa imperatif.

tentang sebuah algoritma yang pada bahasa pemrograman fungsional non-malas memiliki kompleksitas , sedangkan algoritma yang sama dalam pemrograman imperatif adalah Ω ( n ) . Menambahkan kemalasan ke bahasa FP akan membuat algoritma Ω ( n ) .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

Saya ingin melihat referensi ini. Asumsi yang biasa adalah bahwa akses ke array panjang dalam RAM adalah dalam waktu O ( 1 ) dan setara dalam FP murni adalah dalam waktu O ( log n ) . Itu tidak sepenuhnya benar: waktu akses dalam RAM adalah dalam O ( $n$$O(1)$$O(\log n)$ mana m adalah ukuran memori. Tentu saja, m ≥ n . Dalam praktiknya mengakses elemen array jauh lebih cepat. Alasannya adalah bahwa m dibatasi tetapi ... begitu juga n !$O(\log m)$$m$$m≥n$$m$$n$

SUNTING: terima kasih atas tautannya (tautan untuk makalah tentang kemalasan tidak tersedia, berikut ini adalah satu lagi ). Seperti yang diposting di komentar dan di atas dalam jawaban saya, model RAM sedikit tidak adil untuk FP murni dengan memberikan waktu pencarian bahkan ketika ukuran satu alamat tidak dibatasi. Saya belum mengerti bagaimana trik malas bekerja tetapi saya pikir penting untuk dicatat bahwa ini hanya untuk masalah khusus ini.$O(1)$

Itu tergantung pada apa yang Anda maksud dengan ekspresif.

Berikut adalah argumen bahwa orde tinggi memang menambahkan sesuatu: dengan bahasa orde pertama, rekursi primitif tidak cukup untuk mengekspresikan fungsi Ackermann . Namun, dengan adanya fungsi tingkat tinggi, rekursi primitif sudah cukup:

$$\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}$$

Ini mendefinisikan fungsi Ackermann menggunakan rekursi primitif saja.

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