Quản lý cập nhật đối với cấu trúc dữ liệu không thay đổi trong các ngôn ngữ chức năng

Question

Tôi đã nhận thấy trong khi đang tìm kiếm chương trình chức năng có trường hợp danh sách tham số bắt đầu trở nên quá mức khi sử dụng cấu trúc dữ liệu không thay đổi được lồng nhau. Điều này là do khi thực hiện cập nhật cho một trạng thái đối tượng, bạn cần cập nhật tất cả các nút cha trong cấu trúc dữ liệu. Lưu ý rằng ở đây tôi lấy "cập nhật" để có nghĩa là "trả về một đối tượng bất biến mới với thay đổi thích hợp".

ví dụ: các loại chức năng tôi đã tìm thấy bản thân mình bằng văn bản (Clojure chẳng hạn) là:

(defn update-object-in-world [world country city building object property value] 
    (update-country-in-world world 
    (update-city-in-country country 
     (update-building-in-city building 
     (update-object-in-building object property value))))) 

Tất cả điều này để cập nhật một tài sản đơn giản là khá xấu xí, nhưng ngoài người gọi có để lắp ráp tất cả các thông số! Điều này phải là một yêu cầu khá phổ biến khi giao dịch với cấu trúc dữ liệu bất biến trong các ngôn ngữ chức năng nói chung, vì vậy có một mô hình hay thủ thuật tốt để tránh điều này mà tôi nên sử dụng thay thế không? Không.

Answer 1

Có hai phương pháp mà tôi biết:

Thu thập nhiều thông số trong một số loại đối tượng đó là thuận tiện để vượt qua xung quanh. Ví dụ:

; world is a nested hash, the rest are keys 
(defstruct location :world :country :city :building) 
(defstruct attribute :object :property) 

(defn do-update[location attribute value] 
    (let [{:keys [world country city building]} location 
     {:keys [object property]} attribute ] 
    (update-in world [country city building object property] value))) 

này mang đến cho bạn xuống đến hai thông số mà người gọi cần phải quan tâm (vị trí và thuộc tính), có thể là công bằng đủ nếu những thông số không thay đổi rất thường xuyên.

Các thay thế khác là với-X vĩ mô, trong đó đặt ra các biến để sử dụng bởi cơ thể mã:

(defmacro with-location [location & body] ; run body in location context 
    (concat 
    (list 'let ['{:keys [world country city building] :as location} `~location]) 
    `(~@body))) 

Example use: 
(with-location location (println city)) 

Sau đó, bất cứ điều gì cho cơ thể không, nó làm cho thế giới/quốc gia/thành phố/tòa nhà đặt ra cho nó, và nó có thể truyền toàn bộ điều đó sang một chức năng khác bằng cách sử dụng tham số location "được lắp ráp trước".

Cập nhật: Bây giờ với macro có vị trí thực sự hoạt động.

Answer 2

Hãy thử

(update-in 
    world 
    [country city building] 
    (update-object-in-building object property value)) 

Answer 3

Giải pháp đa năng cổ điển cho vấn đề này được gọi là "zipper" data structure. Có một số biến thể, nhưng ý tưởng cơ bản rất đơn giản: Với cấu trúc dữ liệu lồng nhau, hãy tách nó ra khi bạn duyệt qua nó, sao cho mỗi bước bạn có một phần tử "hiện tại" và một danh sách các đoạn biểu diễn cách tái tạo lại phần còn lại của cấu trúc dữ liệu "ở trên" phần tử hiện tại. Một dây kéo có lẽ có thể được coi là "con trỏ" có thể di chuyển qua cấu trúc dữ liệu không thay đổi, thay thế các phần khi nó đi, chỉ tái tạo các phần mà nó có.

Trong trường hợp tầm thường của một danh sách, các mảnh chỉ là các phần tử trước của danh sách, được lưu trữ theo thứ tự ngược lại và việc truyền tải chỉ di chuyển phần tử đầu tiên của danh sách này sang danh sách kia.

Trong trường hợp không phát triển nhưng vẫn đơn giản của cây nhị phân, mỗi mảnh bao gồm một giá trị và một cây con, được xác định là phải hoặc trái. Di chuyển các dây kéo "xuống bên trái" liên quan đến việc thêm vào danh sách các mảnh giá trị của phần tử hiện tại và con phải, làm cho con trái phần tử hiện tại mới. Di chuyển "down-right" hoạt động tương tự, và di chuyển "up" được thực hiện bằng cách kết hợp phần tử hiện tại với giá trị đầu tiên và subtree trên danh sách phân đoạn.

Trong khi ý tưởng cơ bản của dây kéo là rất chung chung, việc xây dựng một dây kéo cho cấu trúc dữ liệu cụ thể thường đòi hỏi một số bit chuyên dụng, chẳng hạn như hoạt động traversal hoặc xây dựng tùy chỉnh.

original paper describing zippers (cảnh báo, PDF) cung cấp mã ví dụ trong OCaml để triển khai lưu trữ các đoạn có đường dẫn rõ ràng thông qua một cây. Không ngạc nhiên, rất nhiều tài liệu cũng có thể được tìm thấy trên dây kéo trong Haskell. Để thay thế cho việc xây dựng một danh sách đường dẫn và phân đoạn rõ ràng, các trình kéo có thể được thực hiện in Scheme using continuations. Và cuối cùng, dường như thậm chí là tree-oriented zipper provided by Clojure.