Apa aplikasi dari pohon Rose?

Saya baru-baru ini mengetahui tentang struktur data pohon Rose, tetapi hanya pergi dari datadefinisi Haskell dan deskripsi Wikipedia kecil itu, saya punya beberapa kesulitan memahami aplikasi apa yang mungkin dimiliki pohon Rose.

Untuk referensi, datadefinisi Haskell :

data RoseTree a = RoseTree a [RoseTree a]

Bagi mereka yang tidak terbiasa dengan Haskell - ini adalah definisi tipe data rekursif dengan tipe arbitrer a, di mana konstruktor tipe dilengkapi dengan tipe literal adiikuti dengan daftar tipe kosong opsional RoseTreepada tipe yang sama a.

Cara saya melihatnya:

• Struktur data ini tidak teratur secara default (meskipun saya menganggap sebagian besar aplikasi praktis menerapkan beberapa bentuk pemesanan untuk pencarian)

• Struktur data tidak menegakkan jumlah tetap node per lapisan pada titik mana pun, kecuali root global, yang harus memiliki satu node

Mengingat jumlah informasi yang minim, saya mengalami kesulitan mencari tahu ketika seseorang mungkin menggunakan jenis pohon ini.

Selain pertanyaan dalam judul, jika pencarian memang diterapkan di sebagian besar aplikasi pohon Mawar, bagaimana hal ini dilakukan?

Anda tampaknya memiliki pola pikir "struktur data dan algoritma" yang terlalu berlebihan. Tidak setiap pohon adalah semacam pohon pencarian. Struktur data sering dirancang untuk sesuai atau menangkap aspek model domain.

S-ekspresi hampir persis pohon mawar. (Atau lebih tepatnya, saya akan mengatakan bagaimana mereka biasanya dianggap sebagai pohon mawar. Wikipedia benar dalam mengatakan mereka lebih seperti pohon biner, tetapi apa yang Anda sebut "benar" S-ekspresi hanya sedikit berbeda dari pohon mawar.) Bagaimanapun, Anda dapat menggunakannya sebagai representasi umum untuk pohon sintaksis abstrak. Manfaat melakukan ini adalah Anda dapat dengan mudah menulis operasi generik, misalnya "temukan semua variabel" atau "parameter swap" atau "ganti nama simbol ini". Ini juga dapat diperluas dalam menambahkan tipe baru node ke sintaksis abstrak Anda sering tidak memerlukan perubahan apa pun. Kelemahannya sebenarnya tidak ada kendala, jadi itu bukan apriori yang mencegah Anda menulis omong kosong. Ini dapat dikurangi untuk pengguna dengan teknik tipe data abstrak standar, tetapi pelaksana transformasi dan semacamnya harus berurusan dengan representasi yang tidak terstruktur meskipun mereka "tahu" bahwa input disusun melalui invarian tipe data. Tentu saja, ketika kepastian itu salah tempat (mungkin karena hal-hal telah berubah), kesalahan cenderung tidak dapat diprediksi dan sulit untuk di-debug.

Dalam praktiknya, sementara Data.Treemodul di perpustakaan standar menyediakan pohon mawar, hampir tidak ada yang menggunakannya di komunitas Haskell. Menentukan tipe data khusus yang secara eksplisit menangkap kendala sangat mudah sehingga hanya ada sedikit alasan untuk menggunakan tipe perpustakaan umum. Lebih jauh, ada sejumlah besar penelitian dan praktik seputar melakukan operasi generik terhadap tipe kustom yang menghilangkan banyak manfaat menggunakan representasi generik. Akhirnya, Haskellers cenderung sangat mendukung kendala eksplisit dan ditegakkan dan bersedia membayar untuk mendapatkannya.

Untuk menjawab pertanyaan terakhir Anda, seringkali mencari AST tidak penting dan / atau AST umumnya dianggap cukup kecil sehingga hanya berjalan semuanya dapat diterima. Memang, tidak jarang untuk mengumpulkan definisi dalam struktur data terpisah dengan referensi ke AST yang dapat dilihat sebagai semacam indeks. Demikian pula, beberapa pass optimasi akan (biasanya secara lokal dan sementara) membangun indeks untuk menyederhanakan dan mempercepat operasi mereka. Struktur AST sesuai dengan input sehingga tidak dapat "diseimbangkan kembali" atau semacamnya. Karena itu, tidak biasa bagi AST itu sendiri berisi informasi pengindeksan atau informasi untuk membantu "pencarian".