глубина накопления первого дерева обхода в Clojure

Question

Я хотел бы взять древовидную структуру, как это:

{"foo" {"bar" "1" "baz" "2"}} 

и рекурсивно траверсы, помня путь от корня, чтобы произвести что-то вроде этого:

["foo/bar/1", "foo/baz/2"] 

Любые предложения о том, как это можно сделать без застежек-молний или clojure.walk?

Answer 1

Я сделал что-то реальное быстрое использование аккумулятора, но это не глубина в первую очередь.

(defn paths [separator tree] 
    (let [finished? (fn [[_ v]] ((complement map?) v))] 
    (loop [finished-paths nil 
      path-trees (seq tree)] 
     (let [new-paths (mapcat 
         (fn [[path children]] 
          (map 
          (fn [[k v]] 
           (vector (str path separator k) v)) 
          children)) 
         path-trees) 
      finished (->> (filter finished? new-paths) 
           (map 
           (fn [[k v]] 
            (str k separator v))) 
           (concat finished-paths)) 
      remaining-paths (remove finished? new-paths)] 
     (if (seq remaining-paths) 
      (recur finished remaining-paths) 
      finished))))) 

В РЕПЛ

(clojure-scratch.core/paths "/" {"foo" {"bar" {"bosh" "1" "bash" "3"} "baz" "2"}}) 
=> ("foo/baz/2" "foo/bar/bash/3" "foo/bar/bosh/1") 

Answer 2

Следующий использует рекурсивные глубины первого обход:

(defn combine [k coll] 
    (mapv #(str k "/" %) coll)) 

(defn f-map [m] 
    (into [] 
     (flatten 
     (mapv (fn [[k v]] 
       (if (map? v) 
        (combine k (f-map v)) 
        (str k "/" v))) 
       m)))) 

(f-map {"foo" {"bar" "1" "baz" "2"}}) 
=> ["foo/bar/1" "foo/baz/2"] 

Answer 3

Вот мое взятие:

(defn traverse [t] 
    (letfn [(traverse- [path t] 
      (when (seq t) 
       (let [[x & xs] (seq t) 
        [k v] x] 
       (lazy-cat 
        (if (map? v) 
        (traverse- (conj path k) v) 
        [[(conj path k) v]]) 
        (traverse- path xs)))))] 
    (traverse- [] t))) 

(traverse {"foo" {"bar" "1" "baz" "2"}}) 
;=> [[["foo" "bar"] "1"] [["foo" "baz"] "2"]] 

Traverse возвращает ленивые последующие статьи пути -кратные пары. Затем можно применить любое преобразование к каждому пути-листа, например, в «/ путь/к/лист» Форма FULLPATH:

(def ->full-path #(->> (apply conj %) (clojure.string/join "/"))) 

(->> (traverse {"foo" {"bar" "1" "baz" "2"}}) 
    (map ->full-path)) 
;=> ("foo/bar/1" "foo/baz/2") 

(->> (traverse {"foo" {"bar" {"buzz" 4 "fizz" "fuzz"} "baz" "2"} "faa" "fee"}) 
    (map ->full-path)) 
;=> ("foo/bar/buzz/4" "foo/bar/fizz/fuzz" "foo/baz/2" "faa/fee") 

Answer 4

Как nberger делает, мы выделим перечисляющем пути от представления их как строки.

Перечень

Функция

(defn paths [x] 
    (if (map? x) 
    (mapcat (fn [[k v]] (map #(cons k %) (paths v))) x) 
    [[x]])) 

... возвращает последовательность пути-последовательностей вложенной карте. Например,

(paths {"foo" {"bar" "1", "baz" "2"}}) 
;(("foo" "bar" "1") ("foo" "baz" "2")) 

Презентация

Функция

#(clojure.string/join \/ %) 

... соединяет строки вместе с "/" с. Например,

(#(clojure.string/join \/ %) (list "foo" "bar" "1")) 
;"foo/bar/1" 

компоновать, чтобы получить нужную вам функцию:

(def traverse (comp (partial map #(clojure.string/join \/ %)) paths)) 

...или просто

(defn traverse [x] 
    (->> x 
     paths 
     (map #(clojure.string/join \/ %)))) 

Например,

(traverse {"foo" {"bar" "1", "baz" "2"}}) 
;("foo/bar/1" "foo/baz/2") 

---

• Вы можете вплетать их в качестве одной функции: более четкой и полезной для разделить их, я думаю.
• Перечисление не является ленивым, поэтому он будет исчерпан пространство стека на достаточно глубоко вложенных картах.

Answer 5

Это моя попытка, используя tree-seq clojure core function.

(def tree {"foo" {"bar" "1" "baz" "2"}}) 

(defn paths [t] 
    (let [cf (fn [[k v]] 
       (if (map? v) 
       (->> v 
         (map (fn [[kv vv]] 
          [(str k "/" kv) vv])) 
         (into {})) 
       (str k "/" v)))] 
    (->> t 
     (tree-seq map? #(map cf %)) 
     (remove map?) 
     vec))) 

(paths tree) ; => ["foo/bar/1" "foo/baz/2"] 

Ключ-карты используются для накопления путей.