Chu kỳ con trỏ trong clojure

Question

Tôi đang viết chương trình clojure phân tích cú pháp XML. Là một phần của điều này, tôi muốn tạo một cây của các nút trong tài liệu XML, dựa trên hàm clojure.xml/parse. Tuy nhiên, tôi muốn cây là bi-directional - nghĩa là, mỗi nút có một danh sách các con, và một con trỏ đến cha của nó. Chỉ có một vấn đề: tất cả dữ liệu là không thay đổi, và vì vậy tôi không thể 'thêm' một con trỏ vào cha mẹ mà không thay đổi con, do đó làm cho con trỏ của phụ huynh vô dụng.

tôi đã tìm thấy câu trả lời này: How can one create cyclic (and immutable) data structures in Clojure without extra indirection?

Các giải pháp đề nghị dường như được tạo ra một bản đồ chỉ số riêng biệt, trong đó đề cập tới các đối tượng bên trong. Điều này có vẻ như một lượng lớn công việc cho một giải pháp tồi tệ hơn nhiều. Tôi không có vấn đề gì về cây để có thể thay đổi được trong quá trình xây dựng, tuy nhiên tôi không thể tìm ra cách nó có thể được thực hiện như thế nào. Có thực sự không có cách nào để có được một con trỏ tuần hoàn trong clojure?

Cảm ơn!

Answer 1

Về mặt logic, không thể làm cho cấu trúc không thay đổi thuần túy theo chu kỳ, vì bằng cách thêm một con trỏ cha hoặc con bạn sẽ làm thay đổi cấu trúc.

Có một hack hoạt động mặc dù tôi không chắc chắn tôi muốn giới thiệu nó: bạn có thể đặt các nguyên tử bên trong cấu trúc dữ liệu Clojure và sau đó biến đổi chúng để tạo các liên kết cần thiết. ví dụ.

(def parent {:id 1 :children (atom nil) :parent (atom nil)}) 

(def child {:id 2 :children (atom nil) :parent (atom nil)}) 

(swap! (:children parent) conj child) 
(reset! (:parent child) parent) 

;; test it works 
(:id @(:parent child)) 
=> 1 

Đây là khó chịu trong tất cả các loại cách:

• Nó sẽ gây ra REPL của bạn để ngăn xếp tràn nếu bạn cố gắng và in một trong những vì REPL là không hy vọng cấu trúc dữ liệu theo chu kỳ.
• Có thể thay đổi được, vì vậy bạn mất tất cả khả năng bảo trì và đồng thời của cấu trúc dữ liệu không thay đổi (đó là một trong những điều tuyệt vời nhất về Clojure!)
• Bạn sẽ cần phải sao chép toàn bộ nút nếu muốn sao chép nó (ví dụ: xây dựng một tài liệu XML mới), vì nó không phải là một giá trị bất biến nữa.
• Dereferencing tất cả các nguyên tử có thể lộn xộn khi bạn điều hướng cấu trúc.
• Bạn sẽ nhầm lẫn những người quen với Clojure thành ngữ.

Vì vậy, nếu bạn thực sự muốn làm điều đó ......... Bạn có lẽ có thể sử dụng một cái gì đó giống như các vị trí kiểu XPath trong tài liệu nếu bạn muốn điều hướng cấu trúc.

Answer 2

Something như thế này có thể làm việc:

(defprotocol TreeItemConstruction 
    (add-child [this child])) 

(deftype MyTree 
    [parent ^:unsynchronized-mutable children] 
    TreeItemConstruction 
    (add-child [this child] 
    (locking this 
     (set! children (conj children child))))) 

(defn my-tree 
    [parent] 
    (->MyTree parent [])) 

(def root (my-tree nil)) 
(def children (repeatedly 5 #(my-tree root))) 
(doseq [child children] (add-child root child)) 

Tận dụng giao thức không nằm trong API công cộng và không bao giờ chạm vào lĩnh vực có thể thay đổi sau khi xây dựng và về cơ bản bạn có một cây không thay đổi. Tuy nhiên việc sửa đổi cây nói sau khi xây dựng sẽ khó khăn. YMMV.

Answer 3

Bạn đã cân nhắc sử dụng zippers?

Dây khóa kéo được thiết kế để cho phép làm việc với cây như cấu trúc một cách hiệu quả. Nó bao gồm các hoạt động cơ bản như nhìn vào children và tại parent của một nút trong khi cũng cho phép easily iterating thông qua cấu trúc.

Dây kéo là các chức năng khá chung chung và được bao gồm đã cho phép tạo chúng từ XML. Một ví dụ trên trang Other Libraries cung cấp một bức tranh ban đầu tốt về cách làm việc với chúng.

Đối với một dây kéo XML, bạn sẽ muốn sử dụng

(clojure.zip/xml-zip (clojure.xml/parse file)) 

để tạo ra các cấu trúc ban đầu. Khi bạn hoàn tất, chỉ cần gọi root để có cấu trúc kết thúc.