Mengapa pemrograman fungsional belum meneliti pohon dinamis?

19

Pohon dinamis memainkan peran penting dalam menyelesaikan masalah seperti aliran jaringan, grafik dinamis, masalah kombinatorial ("Dynamic Trees in Practice" oleh Tarjan dan Werneck) dan baru-baru ini menggabungkan kamus ("A Simple Mergeable Dictionary" oleh Adam Karczmarz),

Dengan pohon dinamis, saya merujuk pada definisi yang dinyatakan dalam makalah Sleator & Tarjan "Struktur data untuk pohon dinamis" pada tahun 1983. Beberapa upaya telah dipublikasikan dalam area penelitian pemrograman fungsional sejak itu.

  1. Edward Kmett mengimplementasikan versi pohon ST sebagian besar sebagai terjemahan dari mitra C ++, lihat Pohon yang terpotong tautan .
  2. Chris Okasaki menulis implementasi terbatas pohon Splay dalam bukunya yang terkenal "Struktur data murni fungsional".
  3. Ralf Hinze dan Ross Paterson memperkenalkan struktur data fungsional yang disebut pohon 2-3 jari tetapi dengan tujuan yang agak berbeda dari definisi asli pohon dinamis.

Implementasi (dan mungkin kinerja) pohon dinamis dibagi berdasarkan tiga pendekatan:

  1. Linearisasi, di mana pohon ET (tur Euler) memainkan peran besar. Tidak ditemukan studi yang murni fungsional.
  2. Path-decomposition, di mana pohon ST adalah andalannya, baru saja menemukan versi Kmett.
  3. Kontraksi pohon, di mana pohon Top, pohon topologi dan pohon RC adalah pemain. Tidak ditemukan studi yang murni fungsional.

Analisis dan implementasi yang murni fungsional dapat ditemukan pada Splay, AVL, pohon merah-hitam, tetapi itu BUKAN pohon dinamis. Yang pertama dianggap bayangan (juga disebut virtual atau tambahan) struktur data yang terakhir.

Jadi, pertanyaan saya adalah:

Apa alasan (kelemahan, kelemahan) bagi komunitas penelitian Pemrograman Fungsional untuk tidak mengambil bagian dalam struktur data pohon dinamis?

data-structures trees functional-programming Richard Chambers
sumber
14
Saya tidak mengerti bagaimana hal ini dapat dijawab tanpa membentuk Komite Komunitas Pemrograman Fungsional yang Berwenang untuk Membentuk Pendapat Resmi. Tidak bisakah kita merumuskan kembali pertanyaan sehingga ada sesuatu yang dapat dijawab di sini? Sejauh yang saya tahu, OP harus pergi dan menerapkan pohon dinamisnya di Haskell atau apa pun dan kemudian kembali ke sini untuk melaporkan bahwa itu telah dilakukan.
Andrej Bauer
Pembaruan ke @AndrejBauer: OP telah pergi dan menerapkan pohon dinamisnya di Haskell: arxiv.org/abs/1908.11105
jbapple

Jawaban:

-1

"Dalam ilmu komputer, pemrograman fungsional adalah paradigma pemrograman. Gaya membangun struktur dan elemen program komputer yang memperlakukan komputasi sebagai evaluasi fungsi matematika dan menghindari perubahan keadaan dan data yang bisa berubah." - Wikipedia

"mengubah status dan data yang bisa berubah" dengan kata lain "dinamis".

Jadi pertanyaan Anda agak seperti bertanya mengapa kiri tidak benar.

Anthony Bachler
sumber
1
Program fungsional dapat mewakili data dinamis dengan struktur data persisten. Pertanyaan ini menanyakan mengapa pengembangan struktur data persisten untuk masalah tertentu belum diteliti. Pertanyaan itu masuk akal.
Reinstate Monica