Apa saja pertanyaan luar biasa dalam struktur data yang murni fungsional?

51

Pertanyaan ini terinspirasi oleh pertanyaan lain tentang apa yang baru dalam PFDS sejak penerbitan buku Okasaki pada tahun 1998 .

Saya akan mulai dengan dua pertanyaan yang saya miliki:

  • Apakah ada struktur data set fungsional murni yang mendekati kecepatan tabel hash? Mencoba belum ada di sana.
  • Apakah ada pohon jari yang berfungsi murni dengan O (1) ditambahkan? Sejauh ini yang terbaik adalah O (lg lg n), dirancang oleh Kaplan dan Tarjan.

Apa masalah struktur data murni fungsional lainnya yang terbuka?

jbapple
sumber
Saya mengerti maksud Anda mencoba seperti di pohon hash daripada kamus yang lebih umum dengan kunci yang berurutan? FWIW, saya pikir tidak mungkin untuk mendekati tabel hash lama yang baik di sini.
Jon Harrop

Jawaban:

19

Saya akan menafsirkan pertanyaan dengan agak bebas. Untuk struktur data gaya Okasaki, memoisasi adalah bentuk mutasi implisit yang memiliki efek samping pada waktu berjalan. Jadi saya akan mengambil pertanyaan untuk memperhatikan struktur data persisten dalam arti yang ketat daripada struktur data dengan implementasi murni fungsional, yang merupakan bagian dari yang sebelumnya. Maksud saya adalah Anda harus dapat mengakses versi lama dari struktur data tanpa penalti, pohon versi dapat bercabang secara sewenang-wenang, dll

Dalam konteks itu, saya menganggap UNION-FIND yang gigih sebagai masalah terbuka yang penting. Ada kertas Conchon-Filliâtre yang disebutkan di utas lainnya. Seorang komentator telah mengemukakan masalah dengan apa yang disebut array persisten mereka: itu benar-benar hanya semi-persisten. Tapi misalkan Anda menggantinya dengan hash trie atau array lain yang benar-benar persisten yang berperilaku lebih baik dalam kasus terburuk (dan bisa dibilang rata-rata) tetapi lebih buruk dalam kasus terbaik. Itu masih menyisakan masalah penting:

Makalah ini memberikan bukti formal kebenaran dalam Coq. Tetapi mereka gagal mengatasi kompleksitas yang diamortisasi baik secara formal maupun informal. Sangat tidak jelas bagi saya bahwa mutasi di balik layar yang rumit menghasilkan kerumitan yang diamortisasi dalam semua kasus. Ketika saya berpikir terakhir tentang hal itu, saya merasa agak percaya diri bahwa saya dapat membuat contoh tandingan jika saya berusaha keras untuk itu. Bahkan jika saya salah tentang bagian terakhir itu, ketiadaan analisis yang tepat adalah kesenjangan besar; jelas bahwa analisis amortisasi klasik Trajan tentang UNION-FIND tidak secara langsung ditransfer.

Per Vognsen
sumber
5
Satu kandidat untuk array yang persisten sepenuhnya (tapi tidak persisten) disajikan dalam Confluently Persistent Tries untuk Kontrol Versi yang Efisien . Penulis mengklaim perlambatan O (lg lg n), mengalahkan perlambatan Dietz dkk O (lg lg m), di mana m adalah jumlah operasi yang telah dilakukan pada array.
jbapple
1
Saya juga akan menambahkan bahwa, meskipun struktur amortisasi malas milik Okasaki seringkali jauh lebih sederhana daripada alternatifnya, saya tidak tahu adanya struktur data yang dapat diimplementasikan dengan cara yang juga tidak dapat diimplementasikan (dengan batas waktu yang sama, tetapi terburuk) dengan cara yang benar-benar murni fungsional.
jbapple
12

Apa masalah struktur data murni fungsional lainnya yang terbuka?

Ini dia:

Apa yang setara dengan fungsi murni dari tabel hash yang lemah?

Jon Harrop
sumber
15
um .... OP telah menanyakan pertanyaan yang belum terjawab, jadi ini akan memenuhi syarat sebagai jawaban potensial untuk pertanyaan OP.
Jason S
6
Oke, saya akan gigit. Apa tabel hash yang lemah?
Jeffε
4
Ini adalah tabel hash yang memungkinkan elemen-elemennya menjadi sampah yang dikumpulkan jika hanya itu (dan peta lemah lainnya) berisi referensi untuknya.
Havvy
3
@ JonHarrop: mudah untuk membuktikan bahwa versi murni dari referensi yang lemah tidak mungkin, karena referensi yang lemah membuat semantik bahasa nondeterministik dan bahasa yang berfungsi murni bersifat deterministik. Jika Anda juga menandai nondeterminisme dalam tipe maka implementasi yang biasa berfungsi. Anda memerlukan tipe dependen (untuk membuktikan bahwa suatu implementasi memberikan jawaban yang sama terlepas dari isi referensi) jika Anda ingin menyembunyikan efek dengan aman.
Neel Krishnaswami
5
@NeelKrishnaswami, saya tidak berpikir itu masalahnya. Anda bisa membuat struktur data yang lemah yang tidak membuat non-determinisme, seperti tabel lemah yang tidak mendukung enumerasi (atau penghitungan). Lihat wiki.ecmascript.org/doku.php?id=harmony:weak_maps untuk contoh.
Sam Tobin-Hochstadt