Bagaimana bahasa pemrograman yang sepenuhnya fungsional berfungsi dengan data yang berubah cepat?

Struktur data apa yang dapat Anda gunakan sehingga Anda bisa mendapatkan O (1) penghapusan dan penggantian? Atau bagaimana Anda dapat menghindari situasi ketika Anda membutuhkan struktur tersebut?

Ada sejumlah besar struktur data yang mengeksploitasi kemalasan dan trik-trik lain untuk mencapai waktu konstan diamortisasi atau bahkan (untuk beberapa kasus terbatas, seperti antrian ) pembaruan waktu konstan untuk berbagai jenis masalah. Tesis PhD Chris Okasaki "Struktur Data Murni Fungsional" dan buku dengan nama yang sama adalah contoh utama (mungkin yang utama pertama), tetapi bidangnya telah maju sejak itu . Struktur data ini biasanya tidak hanya murni dalam antarmuka, tetapi juga dapat diimplementasikan dalam bahasa Haskell murni dan sejenisnya, dan sepenuhnya persisten.

Bahkan tanpa alat canggih ini, pohon pencarian biner seimbang sederhana memberikan pembaruan waktu logaritmik, sehingga memori yang bisa berubah dapat disimulasikan dengan paling buruk memperlambat logaritmik.

Ada beberapa opsi lain, yang mungkin dianggap curang, tetapi sangat efektif terkait dengan upaya implementasi dan kinerja dunia nyata. Misalnya, tipe linier atau tipe keunikan memungkinkan pembaruan di tempat sebagai strategi implementasi untuk bahasa yang secara konseptual murni, dengan mencegah program dari mempertahankan nilai sebelumnya (memori yang akan dimutasi). Ini kurang umum daripada struktur data yang persisten: Misalnya, Anda tidak dapat dengan mudah membuat undo log dengan menyimpan semua versi negara bagian sebelumnya. Itu masih alat yang ampuh, meskipun AFAIK belum tersedia dalam bahasa fungsional utama.

Opsi lain untuk secara aman memperkenalkan keadaan yang bisa berubah ke dalam pengaturan fungsional adalah STmonad di Haskell. Ini dapat diimplementasikan tanpa mutasi, dan unsafe*fungsi pembatasan , berperilaku seolah-olah itu hanya pembungkus mewah sekitar melewati struktur data yang persisten secara implisit (lih State.). Tetapi karena beberapa tipu daya sistem jenis yang menegakkan urutan evaluasi dan mencegah melarikan diri, itu dapat dengan aman diimplementasikan dengan mutasi di tempat, dengan semua manfaat kinerja.

Salah satu struktur yang bisa berubah-ubah murah adalah argumen stack.

Lihatlah perhitungan faktorial gaya SICP yang khas:

(defn fac (n accum) 
    (if (= n 1) 
        accum 
        (fac (- n 1) (* accum n)))

(defn factorial (n) (fac n 1))

Seperti yang Anda lihat, argumen kedua adalah fac digunakan sebagai akumulator yang dapat berubah untuk berisi produk yang cepat berubah n * (n-1) * (n-2) * .... Tidak ada variabel yang dapat berubah yang terlihat, dan tidak ada cara untuk secara tidak sengaja mengubah akumulator misalnya dari utas lainnya.

Ini, tentu saja, adalah contoh terbatas.

Anda bisa mendapatkan daftar tertaut yang tidak dapat diubah dengan penggantian murah dari simpul kepala (dan dengan ekstensi bagian mana saja mulai dari kepala): Anda hanya membuat titik kepala baru ke simpul berikutnya yang sama seperti yang dilakukan kepala lama. Ini bekerja dengan baik dengan banyak algoritma pemrosesan daftar ( foldberbasis apa saja ).

Anda bisa mendapatkan kinerja yang cukup bagus dari array asosiatif berdasarkan misalnya pada HAMT . Secara logis Anda menerima array asosiatif baru dengan beberapa pasangan nilai kunci berubah. Implementasi dapat membagikan sebagian besar data umum antara objek yang lama dan yang baru dibuat. Ini bukan O (1); biasanya Anda mendapatkan sesuatu yang logaritmik, setidaknya dalam kasus terburuk. Pohon yang tidak dapat berubah, di sisi lain, biasanya tidak mengalami penalti performa dibandingkan dengan pohon yang bisa berubah. Tentu saja, ini memerlukan beberapa memori overhead, biasanya jauh dari halangan.

Pendekatan lain didasarkan pada gagasan bahwa jika sebuah pohon tumbang di hutan dan tidak ada yang mendengarnya, itu tidak perlu menghasilkan suara. Artinya, jika Anda dapat membuktikan bahwa sedikit keadaan bermutasi tidak pernah meninggalkan beberapa cakupan lokal, Anda dapat bermutasi data di dalamnya dengan aman.

Clojure memiliki transien yang dapat berubah menjadi 'bayangan' dari struktur data yang tidak berubah yang tidak bocor di luar lingkup lokal. Bersihkan menggunakan Uniques untuk mencapai sesuatu yang serupa (jika saya ingat dengan benar). Rust membantu melakukan hal serupa dengan pointer unik yang dicek secara statis.

Apa yang Anda tanyakan agak terlalu luas. O (1) pemindahan dan penggantian dari posisi mana? Kepala urutan? Ekor? Posisi sewenang-wenang? Struktur data yang digunakan tergantung pada perincian itu. Yang mengatakan, 2-3 Pohon Finger sepertinya salah satu struktur data persisten paling fleksibel di luar sana:

Kami menghadirkan 2-3 pohon jari, representasi fungsional dari sekuens persisten yang mendukung akses ke ujung dalam waktu konstan diamortisasi, dan penggabungan dan pemisahan logaritmik waktu dalam ukuran potongan yang lebih kecil.

(...)

Lebih lanjut, dengan mendefinisikan operasi pemisahan dalam bentuk umum, kami memperoleh struktur data tujuan umum yang dapat berfungsi sebagai urutan, antrian prioritas, pohon pencarian, antrian pencarian prioritas dan banyak lagi.

Struktur data yang persisten umumnya memiliki kinerja logaritmik ketika mengubah posisi sewenang-wenang. Ini mungkin atau mungkin tidak menjadi masalah, karena konstanta dalam algoritma O (1) mungkin tinggi, dan perlambatan logaritmik mungkin "diserap" ke dalam algoritma keseluruhan yang lebih lambat.

Lebih penting lagi, struktur data yang persisten membuat penalaran tentang program Anda lebih mudah, dan itu harus selalu menjadi mode operasi default Anda. Anda harus mendukung struktur data persisten kapan pun memungkinkan, dan hanya menggunakan struktur data yang dapat berubah begitu Anda membuat profil dan menentukan bahwa struktur data persisten adalah hambatan kinerja. Yang lainnya adalah optimasi prematur.