Mengapa daftar struktur data pilihan dalam bahasa fungsional?

Sebagian besar bahasa fungsional menggunakan daftar tertaut sebagai struktur data utama yang tidak dapat diubah. Mengapa daftar, dan bukan pohon misalnya? Pohon juga dapat menggunakan kembali jalur, dan bahkan daftar model.

functional-programming Filip Haglund
sumber

Kemungkinan rangkap dari Mengapa daftar kontra terkait dengan pemrograman fungsional?

nyamuk

@gnat - ini bukan duplikat dari pertanyaan itu. Jawaban yang diterima dan benar untuk pertanyaan itu pada dasarnya adalah "karena daftar tertaut yang tidak dapat diubah memungkinkan berbagi ekor antara daftar yang diperbarui dan yang asli", sebuah jawaban yang ditunjuk sebagai bagian dari latar belakang pertanyaan ini ...

Jules

Satu poin klarifikasi adalah bahwa "daftar" (konsep pemrograman abstrak) berbeda dari "daftar tertaut" (implementasi tertentu dari konsep itu), sangat mirip dengan spesifikasi bahasa pemrograman yang berbeda dari implementasinya. Pertanyaan "mengapa bahasa fungsional menggunakan daftar (konsep pemrograman abstrak) sebagai struktur data utama mereka?" secara halus tetapi secara fundamental sangat berbeda dari pertanyaan "mengapa implementasi umum dari bahasa fungsional X, Y, & Z menggunakan daftar tertaut sebagai struktur data utama mereka?"

Saya scala Vector (yang diimplementasikan sebagai pohon) sedikit lebih disukai untuk Daftar stackoverflow.com/questions/6928327/... Dalam prakteknya kebanyakan orang masih menggunakan Daftar (dari apa yang saya lihat).

Akavall

Saya melakukan beberapa kursus Kursus Pemrograman Fungsional di Scala dan menggunakan BANYAK dengan pohon. Hanya saja daftar itu lebih sederhana untuk contoh. Pohon digunakan untuk masalah kinerja. Anda dapat membuat pohon yang tidak bisa diubah menggunakan kembali bagian dari pohon yang lebih tua sama seperti Anda menambahkan elemen ke daftar yang tidak bisa diubah.

Borjab

Jawaban:

Karena daftar lebih sederhana daripada pohon. (Anda dapat melihat ini sepele dengan fakta bahwa daftar adalah pohon yang merosot, di mana setiap node hanya memiliki satu anak.)

Daftar kontra adalah struktur data rekursif paling sederhana yang mungkin dari ukuran sewenang-wenang.

Guy Steele berpendapat selama desain bahasa pemrograman Fortress bahwa untuk komputasi paralel masif masa depan, baik struktur data kami dan aliran kontrol kami harus berbentuk pohon dengan banyak cabang, tidak linier seperti sekarang. Tetapi untuk saat ini, sebagian besar pustaka struktur data inti kami dirancang dengan pemrosesan berurutan, iteratif (atau rekursi ekor, itu tidak terlalu penting, mereka adalah hal yang sama) dalam pikiran, bukan pemrosesan paralel.

Perhatikan bahwa misalnya dalam Clojure, yang struktur datanya dirancang khusus untuk dunia paralel, terdistribusi, "berawan" saat ini, bahkan array (disebut vektor dalam Clojure), mungkin struktur data yang paling "linier" dari semuanya, sebenarnya diimplementasikan sebagai pohon.

Jadi, singkatnya: daftar kontra adalah struktur data rekursif persisten yang paling sederhana, dan tidak perlu memilih "default" yang lebih rumit. Yang lain tentu saja tersedia sebagai opsi, misalnya Haskell memiliki array, antrian prioritas, peta, heaps, treaps, mencoba, dan semua yang dapat Anda bayangkan, tetapi defaultnya adalah daftar kontra sederhana.

Jörg W Mittag
sumber

Ya, vektor Clojure diimplementasikan sebagai pohon — tetapi perlu dicatat bahwa mereka adalah upaya memetakan array hash , bukan biner standar Anda data Tree a = Leaf a | Branch a (Tree a) (Tree a). Ini memperkuat argumen "kesederhanaan" Anda.

wchargin

Vektor gigih FWIW Clojure diimplementasikan sebagai (seperti @wchargin menunjukkan agak rumit) pohon untuk akses cepat (logaritmik dengan basis besar) dan pembaruan elemen sewenang-wenang, tidak benar-benar untuk operasi paralel per se (bagian permanen mengurusnya untuk beberapa gelar). Bahasa FP lainnya membuat pilihan yang sama (kadang-kadang dengan jenis pohon yang berbeda) ketika mereka menginginkan keduanya (mis. Haskell's Sequenceatau Scala's Vector), tetapi tidak menggunakan pohon ketika mereka hanya perlu membaca karena mereka dapat mencapainya dalam waktu konstan yang benar (mis. Haskell's Vectoratau F # via .Net's ImmutableArray)

badcook

Misalnya pmapping pada vektor di Clojure masih mengakses setiap elemen secara berurutan; struktur pohon vektor umumnya disembunyikan dari pengguna akhir.

badcook

Sebenarnya, daftar itu adalah pohon! Anda memiliki node dengan dua bidang, cardan cdr, yang dapat berisi lebih banyak node, atau daun. Satu-satunya hal yang membuat pohon-pohon ke dalam daftar, adalah konvensi untuk menafsirkan dengan cdrlink yang sebagai link ke node berikutnya dalam daftar linear, dan carhubungan sebagai nilai node saat.

Yang mengatakan, saya kira bahwa prevalensi daftar terkait dalam pemrograman fungsional terkait dengan prevalensi rekursi atas iterasi. Ketika satu-satunya konstruksi looping yang Anda miliki adalah rekursi (tail-), Anda menginginkan struktur data yang mudah digunakan dengan itu; dan daftar tertaut sangat cocok untuk itu.

cmaster
sumber

itu tergantung pada bahasanya. Tentu, Anda dapat menerapkan pohon di LISP-suka menggunakan sel kontra, tetapi di Haskell, misalnya, Anda akan membutuhkan struktur yang sepenuhnya terpisah. Dan juga perhatikan bahwa sebagian besar bahasa fungsional memiliki konstruksi perulangan yang lebih banyak daripada rekursi ekor. Pustaka inti Haskell, misalnya, menyediakan lipatan (kiri dan kanan), pemindaian, lintasan melintasi pohon, iterasi pada kunci dan nilai peta, dan banyak struktur spesialis lainnya. Tentu, mereka diimplementasikan dengan rekursi di belakang layar, tetapi pengguna bahkan tidak perlu memikirkan hal itu untuk membuatnya bekerja.

Jules

@ Jules Namun demikian, pemrograman fungsional dikembangkan dan sangat dipengaruhi oleh bahasa seperti LISP. Jelas, dimungkinkan untuk membuat semua iterasi daftar ini lebih efisien dengan menggunakan array di bawah tenda, atau untuk menambahkan gula sintaksis yang menyembunyikan sifat daftar, tetapi pemrograman fungsional murni dapat dilakukan, dan tidak dilakukan. Juga, Haskell adalah bahasa yang cukup baru (32 tahun lebih muda dari LISP), yang menambahkan sedikit ide lain, gula sintaksis, dll ke gaya fungsional murni. Saya pikir, menilai pemrograman fungsional dengan menilai Haskell agak seperti menilai mixer dengan menilai thermomix ...

cmaster

@cmaster sementara Haskell lebih muda itu masih 27 tahun dan mempengaruhi banyak bahasa (termasuk Python, Java dan C # untuk beberapa nama berpengaruh). Menilai pemrograman fungsional oleh LISP seperti menilai pemrograman imperatif oleh ALGOL - keduanya datang jauh sejak menjadi tidak dapat dikenali. BAIK. Lisp bisa dibilang masih relevan tetapi saya tidak akan menganggapnya 'mainstream' dan kehilangan banyak wawasan kemudian termasuk jenis ML.

Maciej Piechotka

Anda tidak dapat memproses pohon yang ditautkan secara tunggal, secara rekursif atau berulang tanpa tumpukan eksplisit jika Anda ingin menyentuh seluruh pohon, jadi saya tidak berpikir rekursi ekor ada hubungannya dengan itu.

k_g

@MaciejPiechotka Baik Python, Java, atau C # tidak dapat dilihat sebagai bahasa fungsional, mereka sangat penting dan menambahkan beberapa fitur yang terinspirasi oleh pemrograman fungsional. Setelah Anda mengubah keadaan, Anda dengan kuat berada dalam domain program imperatif, bukan fungsional. Saya setuju dengan Anda, bahwa LISP jelas bukan arus utama.

cmaster