Struktur yang tidak berubah dan hierarki komposisi yang dalam

Saya sedang mengembangkan aplikasi GUI, banyak bekerja dengan grafik - Anda dapat menganggapnya sebagai editor vektor, sebagai contoh. Sangat menggoda untuk membuat semua struktur data tidak berubah - sehingga saya bisa membatalkan / mengulang, menyalin / menempel, dan banyak hal lainnya hampir tanpa usaha.

Demi kesederhanaan, saya akan menggunakan contoh berikut - aplikasi digunakan untuk mengedit bentuk poligon, jadi saya memiliki objek "Poligon", yang hanya daftar poin-poin yang tidak dapat diubah:

Scene -> Polygon -> Point

Dan jadi saya hanya punya satu variabel yang bisa berubah-ubah dalam program saya - variabel yang menampung objek Scene saat ini. Masalah yang saya mulai ketika saya mencoba menerapkan menyeret titik - dalam versi bisa berubah, saya hanya mengambil Pointobjek dan mulai memodifikasi koordinatnya. Dalam versi abadi - saya macet. Saya bisa menyimpan indeks Polygonsaat ini Scene, indeks titik yang diseret Polygon, dan menggantinya setiap waktu. Tetapi pendekatan ini tidak skala - ketika tingkat komposisi pergi ke 5 dan lebih jauh, boilerplate akan menjadi tak tertahankan.

Saya yakin masalah ini dapat diselesaikan - lagipula, ada Haskell dengan struktur yang sepenuhnya tidak dapat diubah dan IO monad. Tapi saya tidak bisa menemukan caranya.

Bisakah Anda memberi saya petunjuk?

Saya bisa menyimpan indeks Polygon di Scene saat ini, indeks titik yang diseret dalam Polygon, dan menggantinya setiap waktu. Tetapi pendekatan ini tidak skala - ketika tingkat komposisi pergi ke 5 dan lebih jauh, boilerplate akan menjadi tak tertahankan.

Anda memang benar, pendekatan ini tidak berskala jika Anda tidak bisa menyiasati boilerplate . Secara khusus, pelat untuk membuat Adegan baru dengan bagian kecil berubah. Namun, banyak bahasa fungsional menyediakan konstruksi untuk menangani manipulasi struktur bersarang semacam ini: lensa.

Lensa pada dasarnya adalah pengambil dan penyetel untuk data tidak berubah. Lensa memiliki fokus pada beberapa bagian kecil dari struktur yang lebih besar. Diberikan lensa, ada dua hal yang dapat Anda lakukan dengannya - Anda dapat melihat sebagian kecil dari nilai struktur yang lebih besar, atau Anda dapat mengatur bagian kecil dari nilai struktur yang lebih besar ke nilai baru. Misalnya, Anda memiliki lensa yang berfokus pada item ketiga dalam daftar:

thirdItemLens :: Lens [a] a

Jenis itu berarti struktur yang lebih besar adalah daftar hal-hal, dan bagian kecil adalah salah satunya. Dengan lensa ini, Anda dapat melihat dan mengatur item ketiga dalam daftar:

> view thirdItemLens [1, 2, 3, 4, 5]
3
> set thirdItemLens 100 [1, 2, 3, 4, 5]
[1, 2, 100, 4, 5]

Alasan lensa berguna adalah karena mereka adalah nilai yang mewakili getter dan setter, dan Anda dapat mengabstraksikan mereka dengan cara yang sama seperti Anda dapat nilai lainnya. Anda dapat membuat fungsi yang mengembalikan lensa, misalnya listItemLensfungsi yang mengambil angka ndan mengembalikan lensa yang melihat nitem ke dalam daftar. Selain itu, lensa dapat disusun :

> firstLens = listItemLens 0
> thirdLens = listItemLens 2
> firstOfThirdLens = lensCompose firstLens thirdLens
> view firstOfThirdLens [[1, 2], [3, 4], [5, 6], [7, 8]]
5
> set firstOfThirdLens 100 [[1, 2], [3, 4], [5, 6], [7, 8]]
[[1, 2], [3, 4], [100, 6], [7, 8]]

Setiap lensa merangkum perilaku untuk melintasi satu tingkat struktur data. Dengan menggabungkannya, Anda dapat menghilangkan pelat ketel untuk melintasi beberapa tingkat struktur kompleks. Misalnya, seandainya Anda memiliki scenePolygonLens iyang melihat iPoligon ke dalam suatu Scene, dan polygonPointLens nyang melihat nthTitik dalam Poligon, Anda dapat membuat konstruktor lensa untuk fokus pada titik tertentu yang Anda pedulikan di seluruh adegan seperti:

scenePointLens i n = lensCompose (polygonPointLens n) (scenePolygonLens i)

Sekarang anggaplah pengguna mengklik titik 3 poligon 14 dan memindahkannya 10 piksel ke kanan. Anda dapat memperbarui adegan Anda seperti:

lens = scenePointLens 14 3
point = view lens currentScene
newPoint = movePoint 10 0 point
newScene = set lens newPoint currentScene

Ini dengan baik berisi semua pelat untuk melintasi dan memperbarui adegan di dalamnya lens, yang perlu Anda perhatikan adalah apa yang ingin Anda ubah titiknya. Anda dapat lebih lanjut mengabstraksi ini dengan lensTransformfungsi yang menerima lensa, target, dan fungsi untuk memperbarui tampilan target melalui lensa:

lensTransform lens transformFunc target =
  current = view lens target
  new = transformFunc current
  set lens new target

Ini mengambil fungsi dan mengubahnya menjadi "pembaru" pada struktur data yang rumit, menerapkan fungsi hanya pada tampilan dan menggunakannya untuk membangun tampilan baru. Jadi kembali ke skenario memindahkan titik ke-3 dari poligon ke-14 ke 10 piksel yang tepat, yang dapat dinyatakan dalam bentuk lensTransformseperti ini:

lens = scenePointLens 14 3
moveRightTen point = movePoint 10 0 point
newScene = lensTransform lens moveRightTen currentScene

Dan hanya itu yang Anda butuhkan untuk memperbarui seluruh adegan. Ini adalah ide yang sangat kuat dan bekerja dengan sangat baik ketika Anda memiliki beberapa fungsi yang bagus untuk membuat lensa yang melihat bagian-bagian dari data yang Anda pedulikan.

Namun ini semua sangat luar biasa saat ini, bahkan di komunitas pemrograman fungsional. Sulit untuk menemukan dukungan perpustakaan yang baik untuk bekerja dengan lensa, dan bahkan lebih sulit untuk menjelaskan bagaimana mereka bekerja dan apa manfaatnya bagi rekan kerja Anda. Ambil pendekatan ini dengan sebutir garam.

Saya telah mengerjakan masalah yang persis sama (tetapi hanya dengan 3 level komposisi). Ide dasarnya adalah untuk mengkloning, lalu memodifikasi . Dalam gaya pemrograman yang tidak berubah, kloning dan modifikasi harus terjadi bersama, yang menjadi objek perintah .

Perhatikan bahwa dalam gaya pemrograman yang bisa berubah, kloning akan tetap diperlukan:

• Untuk mengizinkan undo / redo
• Sistem tampilan mungkin perlu untuk secara bersamaan menampilkan model "sebelum edit" dan "selama edit", tumpang tindih (sebagai garis hantu), sehingga pengguna dapat melihat perubahan.

Dalam gaya pemrograman yang bisa berubah,

• Struktur yang ada dikloning dalam
• Perubahan dibuat dalam salinan kloning
• Mesin layar diperintahkan untuk membuat struktur lama dalam garis hantu, dan struktur yang dikloning / dimodifikasi dalam warna.

Dalam gaya pemrograman abadi,

• Setiap tindakan pengguna yang menghasilkan modifikasi data dipetakan ke urutan "perintah".
• Objek perintah merangkum modifikasi apa yang harus diterapkan, dan referensi ke struktur asli.
  • Dalam kasus saya, objek perintah saya hanya mengingat indeks titik yang perlu diubah, dan koordinat baru. (Yaitu sangat ringan, karena saya tidak benar-benar mengikuti gaya abadi.)
• Ketika objek perintah dieksekusi, itu menciptakan salinan struktur yang dimodifikasi, membuat modifikasi permanen di salinan baru.
• Saat pengguna melakukan lebih banyak pengeditan, lebih banyak objek perintah akan dibuat.

Objek yang sangat abadi memiliki keuntungan bahwa mengkloning sesuatu secara sederhana hanya membutuhkan menyalin referensi. Mereka memiliki kelemahan yang bahkan membuat perubahan kecil ke objek bersarang sangat membutuhkan membangun contoh baru dari setiap objek di mana ia bersarang. Objek yang dapat berubah memiliki keuntungan bahwa mengubah suatu objek itu mudah - lakukan saja - tetapi mengkloning mendalam suatu objek membutuhkan membangun objek baru yang berisi klon yang dalam dari setiap objek yang bersarang. Lebih buruk lagi, jika seseorang ingin mengkloning suatu objek dan membuat perubahan, mengkloning objek itu, membuat perubahan lain, dll. Maka tidak peduli seberapa besar atau kecil perubahan yang dilakukan, seseorang harus menyimpan salinan seluruh hierarki untuk setiap versi yang disimpan dari keadaan objek. Menjijikan.

Suatu pendekatan yang mungkin layak dipertimbangkan adalah untuk mendefinisikan tipe abstrak "mungkinMutable" dengan tipe turunan yang dapat berubah dan sangat tidak dapat diubah. Semua tipe seperti itu akan menampilkan AsImmutablemetode; memanggil metode itu pada instance objek yang sangat tidak dapat diubah hanya akan mengembalikan instance itu. Menyebutnya pada instance yang bisa berubah akan mengembalikan instance yang sangat tidak dapat diubah yang propertinya adalah snapshot yang sangat tidak dapat diubah dari padanannya dalam aslinya. Jenis yang tidak dapat diubah dengan padanan yang dapat berubah akan menggunakan AsMutablemetode, yang akan membangun contoh yang dapat berubah yang propertinya cocok dengan yang asli.

Mengubah objek yang bersarang di objek yang sangat tidak dapat diubah akan memerlukan terlebih dahulu mengganti objek yang tidak bisa diubah dengan yang bisa berubah, kemudian mengganti properti yang mengandung benda yang akan diubah dengan benda yang bisa berubah, dll. Tetapi membuat perubahan berulang pada aspek yang sama dari objek objek keseluruhan tidak akan memerlukan membuat objek tambahan sampai saat upaya dilakukan untuk memanggil AsImmutableobjek yang bisa berubah (yang akan membuat objek yang bisa berubah bisa berubah, tetapi mengembalikan objek yang tidak dapat diubah yang memegang data yang sama).

Sebagai optimalisasi yang sederhana namun signifikan, setiap objek yang dapat berubah dapat menyimpan referensi yang di-cache ke objek dari tipe yang terkait yang tidak dapat diubah, dan masing-masing tipe yang tidak berubah harus menyimpan cache GetHashCodenilainya. Saat memanggil AsImmutableobjek yang bisa berubah, sebelum mengembalikan objek yang tidak bisa diubah baru, periksa apakah itu cocok dengan referensi yang di-cache. Jika demikian, kembalikan referensi yang di-cache (meninggalkan objek yang tidak dapat diubah baru). Kalau tidak, perbarui referensi yang di-cache untuk menampung objek baru dan mengembalikannya. Jika ini dilakukan, panggilan berulang keAsImmutabletanpa mutasi yang mengintervensi akan menghasilkan referensi objek yang sama. Bahkan jika seseorang tidak menghemat biaya pembuatan instance baru, ia akan menghindari biaya memori untuk menyimpannya. Selanjutnya, perbandingan kesetaraan antara objek yang tidak dapat diubah dapat sangat dipercepat jika dalam banyak kasus item yang dibandingkan adalah referensi-sama atau memiliki kode hash yang berbeda.