Saya sedang membaca satu bab dalam LYAH yang tidak terlalu masuk akal bagi saya. Saya mengerti bahwa ritsleting dapat secara sewenang-wenang melintasi struktur seperti pohon, tetapi saya perlu klarifikasi. Juga, dapatkah resleting digeneralisasikan ke struktur data apa saja?
ds.data-structures
functional-programming
tree
n_ary_crazy
sumber
sumber
Jawaban:
Ritsleting, secara umum, adalah struktur data dengan lubang di dalamnya. Ritsleting digunakan untuk melintasi / memanipulasi struktur data, dan lubang tersebut sesuai dengan fokus traversal saat ini. Biasanya ada juga elemen struktur data yang sedang dipertimbangkan, sehingga seseorang memiliki ritsleting (daftar) dan daftar atau ritsleting (pohon) dan pohon. Ritsleting memungkinkan pemrogram untuk bergerak secara efisien di sekitar struktur data, bahkan mengganti elemen pada fokus. Pasangan ritsleting dan elemen dalam fokus memenuhi kendala bahwa menempatkan elemen pada fokus dalam lubang memberikan struktur data asli.
Ritsleting dapat digeneralisasi ke tipe data induktif sewenang-wenang. Konsep ini dapat didefinisikan dalam mode tipe-diindeks (Lihat tipe-tipe data yang diindeks ). Mereka juga terkait dengan gagasan turunan dari struktur data , dan telah dipelajari dari perspektif Teori Kategori .
sumber
Ritsleting secara umum adalah sepasang hal: itu adalah struktur-dengan-lubang, fokus , mewakili di mana dalam struktur Anda berada, bersama dengan jalan , merekam bagaimana Anda sampai ke fokus itu. (Jalan ini adalah jejak remah roti LYAH.)
Path adalah bagaimana Anda benar-benar menerapkan perubahan pada struktur: "turun, ke kiri, tambahkan nilainya". Dengan berulang kali menerapkan "naik" (
go_updalam makalah Huet ) pada titik ini, Anda dapat menelusuri kembali langkah-langkah Anda dan berakhir dengan salinan baru, mutasi, dari struktur aslinya.Mereka memang dapat digeneralisasi ke struktur lain:
sumber