Saya mempelajari Haskell dan membaca beberapa artikel tentang perbedaan kinerja daftar Haskell dan (masukkan bahasa Anda).

Menjadi seorang pelajar saya jelas hanya menggunakan daftar tanpa memikirkan perbedaan kinerja. Saya baru-baru ini mulai menyelidiki dan menemukan banyak perpustakaan struktur data yang tersedia di Haskell.

Dapatkah seseorang tolong jelaskan perbedaan antara Daftar, Array, Vektor, Sekuens tanpa terlalu dalam dalam teori ilmu komputer tentang struktur data?

Juga, apakah ada beberapa pola umum di mana Anda akan menggunakan satu struktur data, bukan yang lain?

Apakah ada bentuk lain dari struktur data yang saya lewatkan dan mungkin bermanfaat?

Daftar Rock

Sejauh ini struktur data yang paling bersahabat untuk data berurutan di Haskell adalah Daftar

 data [a] = a:[a] | []

Daftar memberi Anda ϴ (1) kontra dan pencocokan pola. Perpustakaan standar, dan untuk yang penting mendahului, penuh fungsi daftar berguna yang harus sampah kode Anda ( foldr, map, filter). Daftar yang gigih , alias murni fungsional, yang sangat bagus. Daftar Haskell tidak benar-benar "daftar" karena mereka coinductive (bahasa lain menyebut stream ini) sehingga hal-hal seperti

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

bekerja dengan luar biasa. Struktur data batuan tidak terbatas.

Daftar di Haskell menyediakan antarmuka seperti iterator dalam bahasa imperatif (karena kemalasan). Jadi, masuk akal bahwa mereka banyak digunakan.

Di samping itu

Masalah pertama dengan daftar adalah bahwa untuk mengindeks ke mereka (!!)membutuhkan waktu ϴ (k), yang menjengkelkan. Juga, penambahan bisa lambat ++, tetapi model evaluasi malas Haskell berarti bahwa ini dapat diperlakukan sebagai sepenuhnya diamortisasi, jika mereka terjadi sama sekali.

Masalah kedua dengan daftar adalah mereka memiliki lokalitas data yang buruk. Prosesor nyata mengeluarkan konstanta tinggi ketika objek dalam memori tidak diletakkan bersebelahan. Jadi, di C ++ std::vectormemiliki "snoc" yang lebih cepat (meletakkan objek di akhir) daripada struktur data daftar terkait murni yang saya ketahui, meskipun ini bukan struktur data yang bertahan sehingga kurang ramah daripada daftar Haskell.

Masalah ketiga dengan daftar adalah mereka memiliki efisiensi ruang yang buruk. Tumpukan pointer ekstra mendorong penyimpanan Anda (dengan faktor konstan).

Urutan Berfungsi

Data.Sequencesecara internal didasarkan pada pohon jari (saya tahu, Anda tidak ingin tahu ini) yang berarti bahwa mereka memiliki beberapa sifat yang bagus

1. Fungsional murni. Data.Sequenceadalah struktur data yang sepenuhnya tahan.
2. Siapkan akses cepat ke awal dan akhir pohon. ϴ (1) (diamortisasi) untuk mendapatkan elemen pertama atau terakhir, atau menambahkan pohon. Pada daftar hal yang paling cepat, Data.Sequencepaling lambat konstan.
3. ϴ (log n) akses ke tengah urutan. Ini termasuk memasukkan nilai untuk membuat urutan baru
4. API berkualitas tinggi

Di sisi lain, Data.Sequencetidak melakukan banyak hal untuk masalah lokalitas data, dan hanya berfungsi untuk koleksi terbatas (lebih sedikit malas daripada daftar)

Array bukan untuk orang yang lemah hati

Array adalah salah satu struktur data paling penting dalam CS, tetapi mereka tidak cocok dengan dunia fungsional murni yang malas. Array menyediakan ϴ (1) akses ke tengah pengumpulan dan faktor lokalitas / faktor konstan yang sangat baik. Tapi, karena mereka tidak cocok dengan Haskell, mereka sulit digunakan. Sebenarnya ada banyak jenis array yang berbeda di pustaka standar saat ini. Ini termasuk array yang sepenuhnya tahan, array yang dapat diubah untuk monad IO, array yang dapat diubah untuk monad ST, dan versi yang tidak kotak dari yang di atas. Untuk lebih lanjut, periksa wiki haskell

Vektor adalah Array yang "lebih baik"

The Data.Vectorpaket menyediakan semua kebaikan array, di tingkat dan bersih yang lebih tinggi API. Kecuali Anda benar-benar tahu apa yang Anda lakukan, Anda harus menggunakan ini jika Anda membutuhkan kinerja seperti array. Tentu saja, beberapa peringatan masih berlaku - array bisa berubah seperti struktur data tidak bermain bagus dalam bahasa malas murni. Namun, kadang-kadang Anda menginginkan kinerja O (1), dan Data.Vectormemberikannya kepada Anda dalam paket yang bisa digunakan.

Anda memiliki opsi lain

Jika Anda hanya ingin daftar dengan kemampuan untuk memasukkan secara efisien di akhir, Anda dapat menggunakan daftar perbedaan . Contoh terbaik dari daftar mengacaukan kinerja cenderung berasal dari [Char]mana pendahuluan telah disebut sebagai String. Chardaftar yang ramah, tetapi cenderung berjalan pada urutan 20 kali lebih lambat dari string C, jadi jangan ragu untuk menggunakan Data.Textatau sangat cepat Data.ByteString. Saya yakin ada perpustakaan berorientasi urutan lainnya yang tidak saya pikirkan saat ini.

Kesimpulan

90 +% dari waktu saya perlu koleksi berurutan dalam daftar Haskell adalah struktur data yang tepat. Daftar seperti iterator, fungsi yang menggunakan daftar dapat dengan mudah digunakan dengan salah satu dari struktur data ini menggunakan toListfungsi yang menyertainya. Di dunia yang lebih baik, pendahuluan akan sepenuhnya parametrik untuk jenis wadah yang digunakannya, tetapi saat ini []mengotori perpustakaan standar. Jadi, menggunakan daftar (hampir) setiap tempat pasti baik-baik saja.
Anda bisa mendapatkan versi parametrik sepenuhnya dari sebagian besar fungsi daftar (dan mulia untuk menggunakannya)

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

Bahkan, Data.Traversablemendefinisikan API yang kurang lebih bersifat universal di "daftar seperti" apa pun.

Namun, meskipun Anda bisa menjadi baik dan hanya menulis kode parametrik sepenuhnya, kebanyakan dari kita tidak dan menggunakan daftar di semua tempat. Jika Anda belajar, saya sarankan Anda juga.

EDIT: Berdasarkan komentar saya menyadari saya tidak pernah menjelaskan kapan harus menggunakan Data.Vectorvs Data.Sequence. Array dan Vektor menyediakan operasi pengindeksan dan pengirisan yang sangat cepat, tetapi pada dasarnya bersifat transien (penting) struktur data. Struktur data fungsional murni suka Data.Sequencedan []biarkan secara efisien menghasilkan nilai baru dari nilai lama seolah-olah Anda telah memodifikasi nilai lama.

  newList oldList = 7 : drop 5 oldList

tidak mengubah daftar lama, dan tidak perlu menyalinnya. Jadi meskipun oldListsangat panjang, "modifikasi" ini akan sangat cepat. Demikian pula

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

akan menghasilkan urutan baru dengan newValueuntuk menggantikan elemen 3000-nya. Sekali lagi, itu tidak merusak urutan lama, itu hanya menciptakan yang baru. Tapi, ini sangat efisien, mengambil O (log (min (k, kn)) di mana n adalah panjang urutan, dan k adalah indeks yang Anda modifikasi.

Anda tidak dapat dengan mudah melakukan ini dengan Vectorsdan Arrays. Mereka dapat dimodifikasi tetapi itu adalah modifikasi imperatif nyata, dan karena itu tidak dapat dilakukan dalam kode Haskell biasa. Itu berarti operasi dalam Vectorpaket yang membuat modifikasi suka snocdan consharus menyalin seluruh vektor jadi perlu O(n)waktu. Satu-satunya pengecualian untuk ini adalah bahwa Anda dapat menggunakan versi yang bisa berubah ( Vector.Mutable) di dalam STmonad (atau IO) dan melakukan semua modifikasi Anda seperti yang Anda lakukan dalam bahasa imperatif. Setelah selesai, Anda "membekukan" vektor Anda untuk berubah menjadi struktur abadi yang ingin Anda gunakan dengan kode murni.

Perasaan saya adalah bahwa Anda harus menggunakan default Data.Sequencejika daftar tidak sesuai. Gunakan Data.Vectorhanya jika pola penggunaan Anda tidak melibatkan banyak modifikasi, atau jika Anda memerlukan kinerja yang sangat tinggi dalam monad ST / IO.

Jika semua pembicaraan tentang STmonad ini membuat Anda bingung: semakin banyak alasan untuk tetap berpegang teguh pada kecantikan Data.Sequence.