Apa yang baru dalam struktur data yang berfungsi murni sejak Okasaki?


Sejak buku Chris Okasaki tahun 1998 "Struktur data murni fungsional", saya belum melihat terlalu banyak struktur data fungsional murni yang menarik muncul; Saya dapat menyebutkan beberapa saja:

  • IntMap (juga ditemukan oleh Okasaki pada tahun 1998, tetapi tidak ada dalam buku itu)
  • Pohon jari (dan generalisasi mereka atas monoids)

Ada juga beberapa cara menarik untuk mengimplementasikan struktur data yang sudah diketahui, seperti menggunakan "tipe bersarang" atau "tipe data aljabar umum" untuk memastikan invarian pohon.

Gagasan baru apa lagi yang muncul sejak 1998 di bidang ini?


20
Pertanyaan yang bagus Saya baru saja meminta seorang siswa untuk menanyakan hal ini, dan tidak tahu jawabannya.
Suresh Venkat

Ini OK untuk di sini, tetapi Anda mungkin mendapatkan jawaban yang lebih baik di Stack Overflow. Jika Anda bertanya di sana, pastikan dan tautkan ke diskusi di sini.
Charles Stewart

3
Haskell Reddit telah melihat ini sehingga akan ada beberapa jawaban bagus yang datang dari sana juga tetapi pertanyaan yang sangat bagus. Baru separuh membaca buku Okasaki, aku sendiri juga memikirkan hal yang sama. +1
Robert Massaioli


Jawaban:


Struktur data baru yang berfungsi murni yang diterbitkan sejak 1998:

  • 2001: Pohon Hash Ideal , dan pendahulunya tahun 2000, Pencarian Trie Efisien Dan Cepat , oleh Phil Bagwell : Tampaknya digunakan sebagai blok bangunan mendasar di perpustakaan standar Clojure.

  • 2001: Teknik Implementasi Sederhana untuk Antrian Pencarian Prioritas , oleh Ralf Hinze : teknik yang sangat sederhana dan indah untuk mengimplementasikan struktur data penting ini (misalnya, berguna dalam algoritma Dijkstra). Implementasinya sangat indah dan mudah dibaca karena banyak menggunakan "pola tampilan".

  • 2002: Bootstrapping array fleksibel satu sisi , oleh Ralf Hinze : Mirip dengan daftar akses acak Okasaki, tetapi mereka dapat disesuaikan untuk mengubah tradeoff waktu antara consdan pengindeksan.

  • 2003: Deques yang dapat disatukan dan tidak dapat disatukan , oleh Radu Mihaescu dan Robert Tarjan : Sebuah pandangan baru tentang beberapa karya yang lebih tua (oleh Kaplan dan Tarjan) yang dikutip oleh Okasaki (Versi terbaru dari karya Kaplan & Tarjan diterbitkan pada tahun 2000 ). Versi ini lebih sederhana dalam beberapa hal.

  • 2005: tumpukan Maxiphobic ( kertas dan kode ), oleh Chris Okasaki : Disajikan bukan sebagai struktur baru yang lebih efisien, tetapi sebagai cara untuk mengajarkan antrian prioritas.

  • 2006: Daftar Fatenisasi Kasus Terburuk Secara Fungsional, Waktu Terbarukan , oleh Gerth Stølting Brodal, Christos Makris, dan Kostas Tsichlas : Menjawab pertanyaan luar biasa dari Kaplan dan Tarjan dengan mendemonstrasikan sebuah struktur dengan memasukkan, mencari, mencari, dan menghapus O (lg n), (1) concat.

  • 2008: Percobaan yang Persisten untuk Kontrol Versi yang Efisien , oleh Erik D. Demaine, Stefan Langerman, dan Eric Harga : Menampilkan beberapa struktur data untuk percobaan yang memiliki navigasi dan modifikasi yang efisien di dekat daun. Beberapa murni berfungsi. Yang lain benar-benar memperbaiki struktur data yang sudah berjalan lama oleh Dietz et al. untuk array sepenuhnya persisten (tetapi tidak persisten atau fungsional murni). Makalah ini juga menyajikan pohon-pohon penghubung yang murni fungsional , kadang-kadang disebut "pohon dinamis".

  • 2010: Algoritme penghapusan murni baru untuk pohon merah-hitam , oleh Matt Might : Seperti algoritma penyisipan pohon merah-hitam Okasaki, ini bukan struktur data baru atau operasi baru pada struktur data, tetapi cara baru yang lebih sederhana untuk tulis operasi yang dikenal.

  • 2012: RRB-Trees: Vektor Tidak Berubah Efisien , oleh Phil Bagwell dan Tiark Rompf : Perpanjangan ke Hash Array Mapped Tries, mendukung gabungan vektor abadi, menyisipkan, pada dan membagi dalam waktu O (lg n), sambil mempertahankan indeks, memperbarui , dan kecepatan penyisipan vektor abadi asli.

Dikenal pada tahun 1997, tetapi tidak dibahas dalam buku Okasaki:

  • Banyak gaya lain dari pohon pencarian seimbang . AVL, abang, peringkat-seimbang, keseimbangan-terikat, dan banyak pohon pencarian seimbang lainnya dapat (dan telah) diimplementasikan secara murni fungsional dengan menyalin jalur. Mungkin pantas disebutkan secara khusus adalah:

    • Biased Search Trees , oleh Samuel W. Bent, Daniel D. Sleator, dan Robert E. Tarjan : Elemen kunci dalam makalah Brodal et al. 2006 dan makalah Demaine et al. 2008.
  • Perangkat tak terbatas yang mengakui pencarian lengkap yang cepat , oleh Martín Escardó : Mungkin bukan struktur data semata .

  • Tiga algoritma pada Braun Trees , oleh Chris Okasaki : Braun tree menawarkan banyak operasi stack dalam kasus terburuk O (lg n). Batas ini dilampaui oleh banyak struktur data lainnya, tetapi pohon Braun memilikiconsoperasi yang malas dalam argumen keduanya, dan dengan demikian dapat digunakan sebagai tumpukan tak terbatas dalam beberapa hal yang tidak dapat dilakukan oleh struktur lain.

  • Tumpukan min-max yang santai: Antrian prioritas dua sisi yang dapat digabungkan dan Tumpukan KD: Antrian prioritas multi-dimensi yang efisien , oleh Yuzheng Ding dan Mark Allen Weiss : Ini kebetulan berfungsi murni, meskipun ini tidak dibahas dalam makalah. . Saya tidak berpikir batas waktu yang dicapai lebih baik daripada yang dapat dicapai dengan menggunakan pohon jari (dari Hinze & Paterson atau Kaplan & Tarjan) sebagai antrian prioritas k-dimensi, tetapi saya pikir struktur Ding & Weiss menggunakan lebih sedikit ruang .

  • The Zipper , oleh Gérard Huet : Digunakan di banyak struktur data lainnya (seperti pohon jari Hinze & Paterson), ini adalah cara untuk mengubah struktur data keluar-masuk.

  • Daftar perbedaan adalah O (1) daftar yang dapat ditutup dengan transformasi O (n) menjadi consdaftar yang biasa . Mereka tampaknya telah dikenal sejak jaman dahulu di komunitas Prolog, di mana mereka memiliki transformasi O (1) ke consdaftar biasa . Transformasi O (1) tampaknya tidak mungkin dalam pemrograman fungsional tradisional, tetapi abstraksi lubang Minamide , dari POPL '98, membahas cara untuk memungkinkan O (1) menambahkan dan O (1) transformasi dalam pemrograman fungsional murni. Berbeda dengan implementasi pemrograman fungsional dari daftar perbedaan, yang didasarkan pada penutupan fungsi, abstraksi lubang pada dasarnya sama (baik dalam penggunaan dan implementasinya) sebagai daftar perbedaan Prolog. Namun, tampaknya selama bertahun-tahun satu-satunya orang yang memperhatikan inisalah satu pengulas Minamide .

  • O(n)Θ(nlgn)Θ(nlgn)Θ(lg2n)

Struktur data yang paling fungsional, sebelum, selama, dan setelah buku Okasaki:

  • O(m)mO(lglgn)

  • 1989: Pohon Pencarian Secara Acak oleh Cecilia R. Aragon dan Raimund Seidel : Ini dibahas dalam pengaturan fungsional murni oleh Guy E. Blelloch dan Margaret Reid-Miller dalam Operasi Pengaturan Cepat Menggunakan Treaps dan oleh Dan Blandford dan Guy Blelloch dalam Operasi Set Fungsional dengan Treaps ( kode). Mereka menyediakan semua operasi ujung jari murni fungsional dan pohon pencarian bias, tetapi membutuhkan sumber keacakan, membuat mereka tidak sepenuhnya berfungsi. Ini juga dapat membatalkan kompleksitas waktu operasi pada treaps, dengan asumsi musuh yang dapat menentukan waktu operasi dan mengulangi yang lama. (Ini adalah alasan yang sama mengapa argumen amortisasi imperatif tidak valid dalam pengaturan persisten, tetapi itu membutuhkan musuh dengan stopwatch)

  • 1997: Skip-tree, struktur data alternatif untuk Skip-list dalam pendekatan bersamaan , oleh Xavier Messeguer dan Menjelajahi Dualitas Antara Daftar Lewati dan Pohon Pencarian Biner , oleh Brian C. Dean dan Zachary H. Jones : Daftar lompatan tidak murni fungsional, tetapi mereka dapat diimplementasikan secara fungsional sebagai pohon. Seperti treaps, mereka membutuhkan sumber bit acak. (Dimungkinkan untuk membuat daftar skip menjadi deterministik, tetapi, setelah menerjemahkannya ke sebuah pohon, saya pikir itu hanyalah cara lain untuk melihat 2-3 pohon.)

  • 1998: Semua struktur diamortisasi dalam buku Okasaki! Okasaki menemukan metode baru ini untuk menggabungkan amortisasi dan struktur data fungsional, yang sebelumnya dianggap tidak kompatibel. Itu tergantung pada memoisasi, yang, seperti yang kadang-kadang Kaplan dan Tarjan sebutkan, sebenarnya adalah efek samping. Dalam beberapa kasus ( seperti PFDS pada SSD karena alasan kinerja ), ini mungkin tidak sesuai.

  • 1998: Daftar Catenable Confluently Persistent Catenable , oleh Haim Kaplan, Chris Okasaki, dan Robert E. Tarjan : Menggunakan modifikasi di bawah kap untuk memberikan O (1) deatenated catenable deques, menghadirkan antarmuka yang sama seperti sebelumnya (murni fungsional, tetapi dengan memoisasi ) versi muncul di buku Okasaki. Kaplan dan Tarjan sebelumnya telah menciptakan struktur kasus terburuk O yang berfungsi murni, tetapi secara substansial lebih rumit.

  • 2007: Seperti disebutkan dalam jawaban lain di halaman ini, struktur data semi-persisten dan persatuan-persisten oleh Sylvain Conchon dan Jean-Christophe Filliâtre

Teknik untuk memverifikasi struktur data fungsional, sebelum, selama, dan setelah buku Okasaki:

Struktur atau analisis data imperatif tidak dibahas dalam buku Okasaki, tetapi terkait dengan struktur data yang murni fungsional:

  • Soft Heap: Antrian Prioritas Perkiraan dengan Tingkat Kesalahan Optimal , oleh Bernard Chazelle : Struktur data ini tidak menggunakan array, dan karenanya telah tergoda dulu saluran IRC #haskell dan kemudian pengguna Stack Overflow , tetapi termasukdeletedalam o (lg n) , yang biasanya tidak mungkin dalam pengaturan fungsional, dan analisis diamortisasi imperatif, yang tidak valid dalam pengaturan fungsional murni.

  • Pohon pencarian biner seimbang dengan O (1) pembaruan jari . Dalam Membuat Struktur Data yang Persisten , James R Driscoll, Neil Sarnak, Daniel D. Sleator, dan Robert E. Tarjan menyajikan metode untuk mengelompokkan node dalam pohon merah-hitam sehingga pembaruan yang terus-menerus hanya membutuhkan ruang O (1). Deques dan pohon jari yang sepenuhnya fungsional yang dirancang oleh Tarjan, Kaplan, dan Mihaescu semuanya menggunakan teknik pengelompokan yang sangat mirip untuk memungkinkan O (1) memperbarui di kedua ujungnya. AVL-tree untuk pencarian lokal oleh Athanasios K. Tsakalidis bekerja dengan cara yang sama.

  • Tumpukan pasangan lebih cepat atau batas yang lebih baik untuk tumpukan pasangan : Sejak buku Okasaki diterbitkan, beberapa analisis baru tentang tumpukan pasangan imperatif telah muncul, termasuk Pairing heaps dengan O (log log n) mengurangi Biaya oleh Amr Elmasry dan Menuju Analisis Akhir dari Pairing Heaps oleh Seth Pettie. Dimungkinkan untuk menerapkan sebagian dari pekerjaan ini pada tumpukan pasangan malas Okasaki.

  • Pohon jari bias deterministik : Dalam Daftar Lompatan yang bias , oleh Amitabha Bagchi, Adam L. Buchsbaum, dan Michael T. Goodrich, sebuah desain disajikan untuk daftar lompatan yang bias deterministik. Melalui lompatan daftar / transformasi pohon yang disebutkan di atas, dimungkinkan untuk membuat pohon pencarian bias deterministik. Daftar lompatan yang bias jari yang dijelaskan oleh John Iacono dan Özgür Özkan dalam Kamus yang Dapat Digabungkan kemudian dimungkinkan pada pohon lompatan yang bias. Pohon jari yang bias disarankan oleh Demaine et al. dalam makalah mereka tentang percobaan yang berfungsi murni (lihat di atas) sebagai cara untuk mengurangi batas waktu dan ruang pada pembaruan jari dalam percobaan.

  • String B-Tree: Struktur Data Baru untuk Pencarian String dalam Memori Eksternal dan Aplikasi-aplikasinya oleh Paolo Ferragina dan Roberto Grossi adalah struktur data yang dipelajari dengan baik yang menggabungkan manfaat percobaan dan B-tree.


5
Saya tidak ingat mencentang kotak "wiki komunitas" pada jawaban ini. Apakah ada cara untuk membatalkannya?
jbapple

7
@ jbapple: setelah sejumlah pengeditan, semua posting menjadi wiki komunitas. Itu ulasan yang mengesankan menyeluruh di sana. Terima kasih.
Phil Miller

29
Daftar hebat! Yang membuat saya berharap Okasaki akan menerbitkan edisi kedua.
Radu GRIGore

4
Perhatikan bahwa Isabelle / HOL dapat menghasilkan kode untuk SML, OCaml, Haskell, Scala. Alat Haskabelle juga dapat mengimpor Haskell ke Isabelle / HOL.
Makarius

2
Terminologi "ekstraksi program" adalah salah satu dari Coq: Anda mengambil bukti konstruktif dan membuat program yang dapat dieksekusi darinya, menghapus beberapa hal. Dalam Isabelle ini disebut "pembuatan kode" dan bekerja secara berbeda, menggunakan spesifikasi HOL sebagai kode semu, bukan buktinya. Ekstraksi bukti dalam Isabelle / HOL menurut Berghofer bekerja seperti Coq, tetapi jarang digunakan akhir-akhir ini.
Makarius

Untuk catatan bagus yang sudah dibuat, saya akan menambahkan Ritsleting .

Huet, Gerard. “Mutiara Fungsional: Ritsleting” Jurnal Pemrograman Fungsional 7 (5): 549-554, September 1997.

Wikipedia: Zipper (struktur data)


4
Ritsleting yang LUAR BIASA. Untuk banyak kasus penggunaan, mereka memungkinkan representasi berbasis pohon menjadi pilihan yang "tepat" untuk banyak jenis data di mana jika tidak, itu akan menjadi sedikit lebih rumit
Carter Tazio Schonwald

1
Contoh penggunaannya untuk manipulasi XML: anti-xml.org/zippers.html
Siput mekanik


Wow, UNION-FIND yang gigih! Terima kasih!
jkff

3
Yah, agak ... Lihat artikelnya.
Radu GRIGore

1
... atau, jika Anda mau, lihat beberapa kode (oleh Matt Parkinson) github.com/septract/jstar/blob/master/src/utils/…
Radu GRIGore

5
Sekarang saya mengerti mengapa komentar "jenis .." memiliki suara positif. Mereka memiliki kinerja yang baik hanya ketika seseorang hampir secara eksklusif tidak menggunakan ketekunan, atau backtracks sepanjang waktu: jika Anda sering menggunakan kedua versi "baru" dan "lama", Anda gagal. Ide rerooting yang keren.
jkff

Tautan Radu sekarang dapat ditemukan di github.com/septract/jstar-old/blob/…
jbapple


Rangemaps

Ini adalah struktur data khusus, tetapi dapat digunakan sebagai pengganti DIET Martin Erwig, dengan properti yang sedikit berbeda, jadi setidaknya ada satu struktur data yang ada untuk membandingkannya. DIET itu sendiri dijelaskan dalam sebuah artikel di JFP pada tahun 1998, jadi mungkin itu tidak termasuk dalam Struktur Data Murni Fungsional.


Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.