Mengapa daftar kontra terkait dengan pemrograman fungsional?

22

Saya perhatikan bahwa sebagian besar bahasa fungsional menggunakan daftar yang terhubung sendiri (daftar "kontra") sebagai jenis daftar yang paling mendasar. Contohnya termasuk Common Lisp, Haskell dan F #. Ini berbeda dengan bahasa umum, di mana jenis daftar asli adalah array.

Mengapa demikian?

Untuk Common Lisp (diketik secara dinamis) saya mendapatkan ide bahwa kontra cukup umum untuk menjadi basis daftar, pohon, dll. Ini mungkin merupakan alasan kecil.

Untuk bahasa yang diketik secara statis, saya tidak dapat menemukan alasan yang bagus, saya bahkan dapat menemukan argumen-kontra:

  • Gaya fungsional mendorong kekekalan, sehingga kemudahan penyisipan daftar yang ditautkan kurang menguntungkan,
  • Gaya fungsional mendorong kekekalan, demikian juga berbagi data; sebuah array lebih mudah untuk dibagikan "sebagian" dari daftar yang ditautkan,
  • Anda dapat melakukan pencocokan pola pada array biasa juga, dan bahkan lebih baik (Anda dapat dengan mudah melipat dari kanan ke kiri misalnya),
  • Selain itu, Anda mendapatkan akses acak gratis,
  • Dan (keuntungan praktis) jika bahasa diketik secara statis, Anda dapat menggunakan tata letak memori biasa dan mendapatkan peningkatan kecepatan dari cache.

Jadi mengapa memilih daftar yang ditautkan?

programming-languages functional-programming list linked-list Kos
sumber
4
Berasal dari komentar pada jawaban @ sepp2k, saya pikir an array is easier to share "partially" than a linked listperlu klarifikasi untuk apa yang Anda maksud. Karena sifat rekursif mereka, yang terjadi adalah kebalikannya seperti yang saya pahami - Anda dapat sebagian membagi daftar yang tertaut dengan lebih mudah dengan meneruskan simpul apa pun di dalamnya, sementara sebuah array perlu menghabiskan waktu membuat salinan baru. Atau dalam hal berbagi data, dua daftar tertaut dapat menunjuk ke akhiran yang sama, yang jelas tidak mungkin dengan array.
Izkata
Jika sebuah array mendefinisikan dirinya sebagai offset, panjang, buffer triple, maka Anda dapat berbagi array dengan membuat array baru dengan offset + 1, length-1, buffer. Atau memiliki tipe array khusus sebagai subarray.
Dobes Vandermeer
@Izkata Ketika berbicara tentang array, kita jarang hanya berarti buffer seperti pointer ke awal memori yang berdekatan di C. Kami biasanya berarti semacam struktur yang menyimpan panjang dan pointer ke awal buffer yang dibungkus. Di bawah sistem seperti itu, operasi pengiris dapat mengembalikan subarray, yang penunjuk buffernya menunjuk di tengah jalan ke buffer (pada elemen pertama dari sub array), dan yang hitungnya sedemikian rupa sehingga angka awal + hitungan memberi Anda elemen terakhir. Operasi pengiris tersebut adalah O (1) dalam ruang dan waktu
Alexander - Reinstate Monica

Jawaban:

22

Faktor yang paling penting adalah bahwa Anda dapat menambahkan ke daftar tunggal yang tidak dapat diubah dalam waktu O (1), yang memungkinkan Anda untuk secara rekursif membangun daftar elemen-n dalam waktu O (n) seperti ini:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

Jika Anda melakukan ini menggunakan array tetap, runtime akan menjadi kuadrat karena setiap consoperasi akan perlu menyalin seluruh array, yang mengarah ke waktu berjalan kuadratik.

Gaya fungsional mendorong kekekalan, demikian juga berbagi data; sebuah array lebih mudah untuk dibagikan "sebagian" dari daftar yang ditautkan

Saya berasumsi dengan berbagi "sebagian" yang Anda maksudkan bahwa Anda dapat mengambil subarray dari array dalam waktu O (1), sedangkan dengan daftar tertaut Anda hanya dapat mengambil ekor dalam waktu O (1) dan yang lainnya membutuhkan O (n). Itu benar.

Namun mengambil ekor sudah cukup dalam banyak kasus. Dan Anda harus memperhitungkan bahwa membuat subarrays yang murah tidak akan membantu Anda jika Anda tidak punya cara membuat array yang murah. Dan (tanpa optimisasi kompiler yang cerdas) tidak ada cara murah untuk membangun array langkah demi langkah.

sepp2k
sumber
Itu tidak benar sama sekali. Anda dapat menambahkan ke array dalam diamortisasi O (1).
DeadMG
10
@DeadMG Ya, tapi tidak untuk array yang tidak berubah .
sepp2k
"sebagian berbagi" - Saya pikir kedua daftar kontra dapat menunjuk ke daftar akhiran yang sama (tidak tahu mengapa Anda menginginkan ini), dan bahwa Anda dapat melewati titik tengah alih-alih awal daftar ke fungsi lain tanpa harus menyalin itu (saya sudah melakukan ini berkali-kali)
Izkata
@Izkata OP berbicara tentang berbagi sebagian array, bukan daftar. Juga saya belum pernah mendengar apa yang Anda gambarkan disebut berbagi parsial . Itu hanya berbagi.
sepp2k
1
@Izkata OP menggunakan istilah "array" tepat tiga kali. Sekali mengatakan bahwa bahasa FP menggunakan daftar tertaut di mana bahasa lain menggunakan array. Sekali mengatakan bahwa array lebih baik dalam berbagi parsial daripada daftar tertaut dan sekali untuk mengatakan bahwa array dapat dicocokkan dengan pola juga (sebagai daftar tertaut). Dalam semua kasus dia membedakan array dan daftar yang terhubung (untuk membuat titik bahwa array akan lebih berguna sebagai struktur data primer dari daftar yang ditautkan, mengarah ke pertanyaannya mengapa daftar terkait lebih disukai di FP), jadi saya tidak melihat bagaimana dia bisa menggunakan istilah secara bergantian.
sepp2k
4

Saya pikir ini turun ke daftar yang agak mudah diimplementasikan dalam kode fungsional.

Skema:

(define (cons x y)(lambda (m) (m x y)))

Haskell:

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

Array lebih sulit dan hampir tidak cantik untuk diimplementasikan. Jika Anda ingin mereka menjadi sangat cepat maka mereka harus ditulis tingkat rendah.

Selain itu, rekursi bekerja jauh lebih baik pada daftar daripada array. Pertimbangkan berapa kali Anda secara rekursif mengonsumsi / membuat daftar vs array yang diindeks.

Pubby
sumber
Saya tidak akan mengatakan itu akurat untuk menyebut versi skema Anda sebagai implementasi dari daftar tertaut. Anda tidak akan dapat menggunakannya untuk menyimpan apa pun selain fungsi. Array juga lebih sulit (sebenarnya tidak mungkin) untuk diimplementasikan dalam bahasa apa pun yang tidak memiliki dukungan built-in untuk mereka (atau potongan memori), sementara daftar tertaut hanya membutuhkan sesuatu seperti struct, kelas, catatan atau tipe data aljabar untuk diimplementasikan. Itu tidak spesifik untuk bahasa pemrograman fungsional.
sepp2k
@ sepp2k Apa maksud Anda "menyimpan apa pun selain fungsi" ?
Pubby
1
Yang saya maksudkan adalah bahwa daftar yang didefinisikan seperti itu tidak dapat menyimpan apa pun yang bukan fungsi. Tapi itu tidak benar. Tak tahu, mengapa saya memikirkan itu. Maaf soal itu.
sepp2k
2

Daftar yang terhubung sendiri adalah struktur data persisten yang paling sederhana .

Struktur data yang persisten sangat penting untuk performan, pemrograman murni fungsional.

ziggystar
sumber
1
ini sepertinya hanya mengulangi poin yang dibuat dan dijelaskan dalam jawaban teratas yang diposting lebih dari 4 tahun yang lalu
agas
3
@gnat: Jawaban teratas tidak menyebutkan struktur data persisten, atau bahwa daftar tertaut tunggal adalah struktur data persisten paling sederhana, atau bahwa mereka sangat penting untuk pemrograman murni yang berfungsi murni. Saya tidak dapat menemukan tumpang tindih dengan jawaban teratas sama sekali.
Michael Shaw
2

Anda dapat menggunakan node Cons dengan mudah hanya jika Anda memiliki bahasa sampah yang dikumpulkan.

Node Kontra sangat cocok dengan gaya pemrograman fungsional panggilan rekursif dan nilai-nilai yang tidak berubah. Jadi sangat cocok dengan model mental programmer.

Dan jangan lupakan alasan historis. Mengapa mereka masih disebut Node Kontra dan lebih buruk lagi menggunakan mobil dan cdr sebagai pengakses? Orang-orang mempelajarinya dari buku pelajaran dan kursus lalu menggunakannya.

Anda benar, dalam array dunia nyata jauh lebih mudah digunakan, hanya mengkonsumsi setengah ruang memori dan jauh lebih berkinerja karena tingkat cache yang meleset. Tidak ada alasan untuk menggunakannya dengan bahasa imperatif.

Lothar
sumber
1

Daftar tertaut penting karena alasan berikut:

Setelah Anda mengambil angka seperti 3, dan mengonversinya menjadi urutan penerus seperti succ(succ(succ(zero))), dan kemudian menggunakan substitusi dengannya {succ=List node with some memory space}, dan {zero = end of list}, Anda akan berakhir dengan daftar tertaut (panjang 3).

Bagian penting sebenarnya adalah angka, substitusi, dan ruang memori dan nol.

tp1
sumber