стохастический обход дерева в Clojure

Question

Учитывая дерево, закодированное как набор вложенных списков (например, (+ 2 (+ 2 1) (+ 1 3 2))), существует ли известный алгоритм в Clojure, который стохастически пересекает дерево, применяя параметрически поставленную функцию в одном узле с равной вероятностью «посадки» на любом узле? Примечание: прогулка заканчивается после преобразования одного узла.

Я ожидаю, что алгоритм должен вести себя следующим образом:

(def tree '(1 (1 (1 1 1) 1) 1)) 
(stochastic-tree-f-app inc tree) => (1 (1 (1 2 1) 1) 1) 
(stochastic-tree-f-app inc tree) => (1 (1 (1 1 2) 1) 1) 
(stochastic-tree-f-app inc tree) => (2 (1 (1 1 1) 1) 1) 
(stochastic-tree-f-app inc tree) => (1 (1 (1 1 1) 1) 2) 
(stochastic-tree-f-app dec tree) => (1 (1 (1 1 1) 0) 1) 

Answer 1

Использование clojure.zip:

(require '[clojure.zip :as z]) 

(defn stochastic-tree-f-app [f tree] 
    (let [zp (z/zipper list? seq (fn [_ c] c) tree) 
     nodes (->> (iterate z/next zp) 
        (take-while (complement z/end?)) 
        (filter (comp integer? z/node)) 
        (into []))] 
    (-> (rand-nth nodes) 
     (z/edit f) 
     z/root))) 

Answer 2

Вы можете просто использовать clojure.walk если последнее требование может быть снято (т.е. ... прогулка заканчивается после того, как один узел преобразуется). Или пройдите по узлам с помощью молнии и завершите редактирование. Использование clojure.walk:

(use 'clojure.walk) 

(def tree '(1 (1 (1 1 1) 1) 1)) 

(defn stochastic-tree-f-app [f tree] 
    (let [cnt (atom 0) 
     _ (postwalk #(if (integer? %) (swap! cnt inc)) tree) 
     idx (rand-int @cnt)] 
    (reset! cnt 0) 
    (postwalk #(if (and (integer? %) (= idx (swap! cnt inc))) 
       (f %) 
       %) 
       tree))) 

user> (stochastic-tree-f-app inc tree) 
(2 (1 (1 1 1) 1) 1) 
user> (stochastic-tree-f-app inc tree) 
(1 (1 (1 1 1) 2) 1)