Biểu thị biểu đồ trong clojure

Question

Tôi đang cố gắng tìm hiểu một chút clojure bằng cách chuyển một đồ chơi NFA regexp matcher. Rõ ràng vấn đề chính của tôi là đại diện và thao tác đồ thị. Tôi nhấn một giải pháp làm việc, nhưng thực hiện của tôi (sử dụng gensym để mô phỏng con trỏ, về cơ bản) lá tôi với một hương vị yucky trong miệng của tôi.

Bạn có thể đề xuất cải tiến, cả hai để đại diện cho đồ thị và cho khả năng đọc và thành ngữ chung? (các giải pháp bắt buộc ban đầu là dễ đọc hơn nhiều so với hiện tại của tôi là).

Chúc mừng!

; This is a port of Matt Might's toy regexp library described in 
; http://matt.might.net/articles/implementation-of-nfas-and-regular-expressions-in-java/ 

; char_transitions is a map that associates a character with a set 
; of target state names 
; empty_transitions is a set of target state names 
(defrecord NfaState [final char_transitions empty_transitions]) 

; 'entry' and 'exit' are state names 
; 'states' is a map that associates state names with states 
(defrecord Nfa [entry exit states]) 

(defn- add-empty-edge [nfa curr_state_name next_state_name] 
    (let [curr_state (curr_state_name (:states nfa))] 
    (Nfa. (:entry nfa) (:exit nfa) (assoc (:states nfa) curr_state_name (NfaState. (:final curr_state) (:char_transitions curr_state) (conj (:empty_transitions curr_state) next_state_name)))))) 

(defn- nfa-matches? 
    ([nfa nfa_state_name string] (nfa-matches? nfa nfa_state_name string #{})) 
    ([nfa nfa_state_name string visited] 
    (let [nfa_state (nfa_state_name (:states nfa)) 
     new_visited (conj visited nfa_state_name)] 
    (cond 
     (contains? visited nfa_state_name) false 
     (empty? string) (or (:final nfa_state) 
          (some #(nfa-matches? nfa % string new_visited) 
           (:empty_transitions nfa_state))) 
     (not (empty? string)) (or 
           (some #(nfa-matches? nfa % (.substring string 1)) (get (:char_transitions nfa_state) (.charAt string 0) #{})) 
           (some #(nfa-matches? nfa % string new_visited) (:empty_transitions nfa_state))) 
     :else false)))) 

(defn matches? [nfa string] 
    "Matches a string against an NFA" 
    (nfa-matches? nfa (:entry nfa) string)) 

(defn c [ch] 
    "Creates an NFA which matches the character 'c'" 
    (let [in (gensym) 
     out (gensym)] 
    (Nfa. in out {in (NfaState. false {ch #{out}} #{}) out (NfaState. true {} #{})}))) 

(defn e [] 
    "Creates an NFA which matches the empty string" 
    (let [in (gensym) 
     out (gensym)] 
    (Nfa. in out {in (NfaState. false {} #{out}) out (NfaState. true {} #{})}))) 

(defn rep [nfa] 
    "Creates an NFA which matches zero or more repetitions of the given NFA" 
    (add-empty-edge (add-empty-edge nfa (:entry nfa) (:exit nfa)) (:exit nfa) (:entry nfa))) 

(defn- update-final [nfastate new_final] 
    (NfaState. new_final (:char_transitions nfastate) (:empty_transitions nfastate))) 

(defn s [first second] 
    "Creates an NFA which matches a sequence of two provided NFAs" 
    (add-empty-edge (Nfa. (:entry first) (:exit second) (merge (update-in (:states first) [(:exit first)] update-final false) (update-in (:states second) [(:exit second)] update-final true))) (:exit first) (:entry second))) 

(defn ou [first second] 
    "Creates an NFA which matches either provided NFA" 
    (let [in (gensym) 
     out (gensym)] 
    (add-empty-edge (add-empty-edge (Nfa. in out (assoc (merge (update-in (:states first) [(:exit first)] update-final false) (update-in (:states second) [(:exit second)] update-final false)) in (NfaState. false {} #{(:entry first) (:entry second)}) out (NfaState. true {} #{}))) (:exit first) out) (:exit second) out))) 

; sugar 
(defn st [string] 
    "Creates an NFA which matches the provided string" 
    (if (empty? string) 
    (e) 
    (s (c (.charAt string 0)) (st (.substring string 1))))) 

Answer 1

Maps và bộ là một dữ liệu tuyệt vời cấu trúc như vậy, vì họ là phát triển durring nhìn thấy và có thể dễ dàng thao tác bằng cách sử dụng zipper library mà bạn có thể tìm thấy hữu ích cho loại vấn đề.