Comment obtenir les chemins vers tous les nœuds enfants dans un arbre qui n'ont que des feuilles à l'aide de fermetures à glissière clojure?

C'est parce que les fermetures à glissière ont tellement de limitations que j'ai créé le Tupelo Bibliothèque forestière pour le traitement des structures de données arborescentes. Votre problème a alors une solution simple:

(format-paths leaf-paths) => 
    [[{:tag "root"} [{:tag "level_a_node3"} [{:tag "leaf"}]]]
     [{:tag "root"} [{:tag "level_a_node2"} [{:tag "level_b_node2"} [{:tag "level_c_node1"} [{:tag "leaf"}]]]]]
     [{:tag "root"} [{:tag "level_a_node2"} [{:tag "level_b_node1"} [{:tag "leaf"}]]]]
     [{:tag "root"} [{:tag "level_a_node1"} [{:tag "leaf"}]]]
     [{:tag "root"} [{:tag "leaf"}]]]))))

avec un arbre qui ressemble à:

(hid->bush root-hid) => 
    [{:tag "root"}
     [{:tag "level_a_node3"}
      [{:tag "leaf"}]]
     [{:tag "level_a_node2"}
      [{:tag "level_b_node2"}
       [{:tag "level_c_node1"}
        [{:tag "leaf"}]]]
      [{:tag "level_b_node1"}
       [{:tag "leaf"}]]]
     [{:tag "level_a_node1"}
      [{:tag "leaf"}]]
     [{:tag "leaf"}]])

et un résultat comme:

(ns tst.tupelo.forest-examples
  (:use tupelo.core tupelo.forest tupelo.test))

  (with-forest (new-forest)
    (let [data          ["root"
                         ["level_a_node3" ["leaf"]]
                         ["level_a_node2"
                          ["level_b_node2"
                           ["level_c_node1"
                            ["leaf"]]]
                          ["level_b_node1" ["leaf"]]]
                         ["level_a_node1" ["leaf"]]
                         ["leaf"]]
          root-hid      (add-tree-hiccup data)
          leaf-paths    (find-paths-with root-hid [:** :*] leaf-path?)]

Il y a beaucoup de choix après cela en fonction des prochaines étapes de la chaîne de traitement.

Les structures de style hoquet sont un endroit agréable à visiter, mais je ne voudrais pas y vivre. Autrement dit, ils sont très succincts à écrire, mais il est très difficile de les manipuler par programme, car la structure d'imbrication sémantique ne se reflète pas dans la structure physique des nœuds. Donc, la première chose que je ferais est de convertir en représentation arborescente de style Enlive (ou, idéalement, de générer Enlive pour commencer):

(defn hiccup-paths-to-leaves [node]
  (when (vector? node)
    (let [tag (first node), content (next node)]
      (if (and content (every? #(= 1 (count %)) content))
        [(list tag)]
        (for [child content
              path (hiccup-paths-to-leaves child)]
          (cons tag path))))))

Après avoir fait cela, la dernière chose qui vous gêne est votre désir d'utiliser des fermetures à glissière. Ils sont un bon outil pour les traversées ciblées, où vous vous souciez beaucoup de la structure près du nœud sur lequel vous travaillez. Mais si vous vous souciez uniquement du nœud et de ses enfants, il est beaucoup plus facile d'écrire simplement une fonction récursive simple pour parcourir l'arbre:

(defn paths-to-leaves [{:keys [tag content] :as root}]
  (when (seq content)
    (if (every? #(empty? (:content %)) content)
      [(list tag)]
      (for [child content
            path (paths-to-leaves child)]
        (cons tag path)))))

La possibilité d'écrire des traversées récursives comme celle-ci est une compétence qui vous servira plusieurs fois tout au long de votre carrière Clojure (par exemple, une question similaire à laquelle j'ai récemment répondu sur Code Review ). Il s'avère qu'un grand nombre de fonctions sur les arbres sont simplement: appelez-vous de manière récursive sur chaque enfant, et combinez d'une manière ou d'une autre les résultats, généralement dans une boucle for éventuellement imbriquée. La partie la plus difficile est simplement de déterminer ce que votre cas de base doit être, et la séquence correcte de cartes / mapcats pour combiner les résultats sans introduire de niveaux d'imbrication indésirables.

Si vous insistez pour rester avec Hiccup, vous peut le démanteler sur le site d'utilisation sans trop de peine:

(def hiccup
  ["root"
   ["level_a_node3" ["leaf432"]]
   ["level_a_node2"
    ["level_b_node2"
     ["level_c_node1"
      ["leaf654"]]]
    ["level_b_node1"
     ["leaf987"]]
    ["leaf789"]]
   ["level_a_node1"
    ["leaf456"]]
   ["leaf123"]])
(defn hiccup->enlive [x]
  (when (vector? x)
    {:tag (first x)
     :content (map hiccup->enlive (rest x))}))
(def enlive (hiccup->enlive hiccup))

;; Yielding...
{:tag "root",
 :content
 ({:tag "level_a_node3", :content ({:tag "leaf432", :content ()})}
  {:tag "level_a_node2",
   :content
   ({:tag "level_b_node2",
     :content
     ({:tag "level_c_node1",
       :content ({:tag "leaf654", :content ()})})}
    {:tag "level_b_node1", :content ({:tag "leaf987", :content ()})}
    {:tag "leaf789", :content ()})}
  {:tag "level_a_node1", :content ({:tag "leaf456", :content ()})}
  {:tag "leaf123", :content ()})}

Mais c'est nettement plus compliqué, et c'est un travail que vous devrez répéter chaque fois que vous travaillez avec un arbre . Encore une fois, je vous encourage à utiliser des arborescences de style Enlive pour la représentation de vos données internes.

Vous pouvez certainement utiliser l'API de fichier pour naviguer dans le répertoire. Si vous utilisez une fermeture éclair, vous pouvez faire ceci:

(->> ["root"
      ["level_a_node3"
      ["leaf432"]]
      ["level_a_node2"
      ["level_b_node2"
        ["level_c_node1"
        ["leaf654"]]]
      ["level_b_node1"
        ["leaf987"]]
      ["leaf789"]]
      ["level_a_node1"
      ["leaf456" "leaf456b"]]
      ["leaf123"]]
     vector-zip
     (iterate next)
     (take-while (complement end?))
     (filter contains-leaves-only?)
     (map #(->> % down path (map node))))

qui affichera ceci:

(def is-leaf? #(-> % down nil?))

(defn contains-leaves-only?
  [loc]
  (some->> loc
           down            ;; branch name
           right           ;; children list
           down            ;; first child
           (iterate right) ;; with other sibiling
           (take-while identity)
           (every? is-leaf?)))

avec la façon dont vous définissez l'arborescence, les fonctions d'assistance peut être mis en œuvre comme:

(("root" "level_a_node1")
 ("root" "level_a_node2" "level_b_node1")
 ("root" "level_a_node2" "level_b_node2" "level_c_node1")
 ("root" "level_a_node3"))

UPDATE - ajouter une version de séquence paresseuse

(loop [loc (vector-zip ["root"
                        ["level_a_node3"
                         ["leaf432"]]
                        ["level_a_node2"
                         ["level_b_node2"
                          ["level_c_node1"
                           ["leaf654"]]]
                         ["level_b_node1"
                          ["leaf987"]]
                         ["leaf789"]]
                        ["level_a_node1"
                         ["leaf456" "leaf456b"]]
                        ["leaf123"]])
       ans nil]
  (if (end? loc)
    ans
    (recur (next loc)
           (cond->> ans
             (contains-leaves-only? loc)
             (cons (->> loc down path (map node)))))))