Dalam pemrograman fungsional, apakah memiliki sebagian besar struktur data yang tidak dapat diubah memerlukan penggunaan memori yang lebih banyak?

Dalam pemrograman fungsional karena hampir semua struktur data tidak dapat diubah, ketika negara harus mengubah struktur baru dibuat. Apakah ini berarti lebih banyak penggunaan memori? Saya tahu paradigma pemrograman berorientasi objek dengan baik, sekarang saya mencoba untuk belajar tentang paradigma pemrograman fungsional. Konsep segala sesuatu yang abadi berubah membingungkan saya. Sepertinya program yang menggunakan struktur yang tidak dapat diubah akan membutuhkan lebih banyak memori daripada program dengan struktur yang bisa berubah. Apakah saya melihat ini dengan cara yang benar?

Satu-satunya jawaban yang benar untuk ini adalah "kadang-kadang". Ada banyak trik yang dapat digunakan bahasa fungsional untuk menghindari pemborosan memori. Kekekalan memudahkan untuk berbagi data antar fungsi, dan bahkan antar struktur data, karena kompiler dapat menjamin bahwa data tidak akan dimodifikasi. Bahasa fungsional cenderung mendorong penggunaan struktur data yang dapat digunakan secara efisien sebagai struktur yang tidak dapat diubah (misalnya, pohon alih-alih tabel hash). Jika Anda menambahkan kemalasan ke dalam campuran, seperti banyak bahasa fungsional lainnya, itu menambahkan cara baru untuk menghemat memori (itu juga menambahkan cara baru membuang-buang memori, tapi saya tidak akan membahasnya).

Dalam pemrograman fungsional karena hampir semua struktur data tidak dapat diubah, ketika negara harus mengubah struktur baru dibuat. Apakah ini berarti lebih banyak penggunaan memori?

Itu tergantung pada struktur data, perubahan tepat yang Anda lakukan dan, dalam beberapa kasus, pengoptimal. Sebagai salah satu contoh, mari kita pertimbangkan untuk menambahkan ke sebuah daftar:

list2 = prepend(42, list1) // list2 is now a list that contains 42 followed
                           // by the elements of list1. list1 is unchanged

Di sini persyaratan memori tambahan konstan - demikian pula biaya runtime panggilan prepend. Mengapa? Karena prependhanya menciptakan sel baru yang memiliki 42kepala dan list1ekornya. Tidak perlu menyalin atau beralih ke sana list2untuk mencapai ini. Artinya, kecuali untuk memori yang diperlukan untuk menyimpan 42, list2menggunakan kembali memori yang sama yang digunakan oleh list1. Karena kedua daftar tidak dapat diubah, berbagi ini sangat aman.

Demikian pula, ketika bekerja dengan struktur pohon seimbang, sebagian besar operasi hanya memerlukan jumlah ruang tambahan logaritmik karena semuanya, tetapi satu jalur pohon dapat dibagi.

Untuk array situasinya agak berbeda. Itu sebabnya, dalam banyak bahasa FP, array tidak begitu umum digunakan. Namun, jika Anda melakukan sesuatu seperti arr2 = map(f, arr1)dan arr1tidak pernah digunakan lagi setelah baris ini, pengoptimal yang pintar benar-benar dapat membuat kode yang bermutasi arr1alih-alih membuat array baru (tanpa mempengaruhi perilaku program). Dalam hal itu pertunjukan akan seperti dalam bahasa imperatif tentu saja.

Implementasi naif memang akan mengekspos masalah ini - ketika Anda membuat struktur data baru alih-alih memperbarui yang sudah ada di tempat, Anda harus memiliki beberapa overhead.

Bahasa yang berbeda memiliki cara berbeda dalam menangani hal ini, dan ada beberapa trik yang sebagian besar digunakan.

Salah satu strategi adalah pengumpulan sampah . Saat struktur baru telah dibuat, atau segera setelah itu, referensi ke struktur lama keluar dari ruang lingkup, dan pengumpul sampah akan mengambilnya secara instan atau segera, tergantung pada algoritma GC. Ini berarti bahwa sementara masih ada overhead, itu hanya sementara, dan tidak akan tumbuh secara linear dengan jumlah data.

Yang lain memilih berbagai jenis struktur data. Di mana array adalah struktur data daftar masuk dalam bahasa imperatif (biasanya dibungkus dalam semacam wadah realokasi-dinamis seperti std::vectordalam C ++), bahasa fungsional sering lebih suka daftar yang ditautkan. Dengan daftar tertaut, operasi prepend ('kontra') dapat menggunakan kembali daftar yang ada sebagai ekor daftar baru, sehingga semua yang benar-benar mendapat alokasi adalah kepala daftar baru. Strategi serupa ada untuk jenis struktur data lainnya - set, tree, sebut saja.

Dan kemudian ada evaluasi malas, à la Haskell. Idenya adalah bahwa struktur data yang Anda buat tidak segera dibuat sepenuhnya; alih-alih, mereka disimpan sebagai "thunks" (Anda dapat menganggap ini sebagai resep untuk membangun nilai saat dibutuhkan). Hanya ketika nilai dibutuhkan maka thunk bisa diperluas menjadi nilai aktual. Ini berarti bahwa alokasi memori dapat ditunda sampai evaluasi diperlukan, dan pada saat itu, beberapa pukulan dapat digabungkan dalam satu alokasi memori.

Saya hanya tahu sedikit tentang Clojure dan itu Struktur Data yang Tidak Berubah .

Clojure menyediakan serangkaian daftar, vektor, set, dan peta yang tidak berubah. Karena tidak dapat diubah, 'menambah' atau 'menghapus' sesuatu dari koleksi yang tidak dapat diubah berarti membuat koleksi baru seperti yang lama tetapi dengan perubahan yang diperlukan. Kegigihan adalah istilah yang digunakan untuk menggambarkan properti tempat versi lama koleksi masih tersedia setelah 'perubahan', dan bahwa koleksi mempertahankan jaminan kinerjanya untuk sebagian besar operasi. Secara khusus, ini berarti bahwa versi baru tidak dapat dibuat menggunakan salinan lengkap, karena itu akan memerlukan waktu linier. Tidak dapat dihindari, koleksi persisten diimplementasikan menggunakan struktur data tertaut, sehingga versi baru dapat berbagi struktur dengan versi sebelumnya.

Secara grafis, kita dapat mewakili sesuatu seperti ini:

(def my-list '(1 2 3))

    +---+      +---+      +---+
    | 1 | ---> | 2 | ---> | 3 |
    +---+      +---+      +---+

(def new-list (conj my-list 0))

              +-----------------------------+
    +---+     | +---+      +---+      +---+ |
    | 0 | --->| | 1 | ---> | 2 | ---> | 3 | |
    +---+     | +---+      +---+      +---+ |
              +-----------------------------+

Selain apa yang telah dikatakan dalam jawaban lain, saya ingin menyebutkan bahasa pemrograman Bersih, yang mendukung apa yang disebut tipe unik . Saya tidak tahu bahasa ini, tetapi saya kira jenis unik mendukung semacam "pembaruan destruktif".

Dengan kata lain, sementara semantik memperbarui keadaan adalah bahwa Anda membuat nilai baru dari yang lama dengan menerapkan fungsi, batasan keunikan dapat memungkinkan kompiler untuk menggunakan kembali objek data secara internal karena ia tahu bahwa nilai lama tidak akan direferensikan lagi dalam program setelah nilai baru telah dihasilkan.

Untuk detail lebih lanjut, lihat mis . Beranda bersih dan artikel wikipedia ini