Étant donné un arbre, comment générer une liste de tous les sous-arbres (appropriés) dans Clojure en utilisant des fonctions d'ordre supérieur?
Arrière-plan
Je travaille sur L'avènement du code 2019 Problème n ° 6 . Le problème commence par une liste de contiguïté . J'ai représenté la liste de contiguïté comme un arbre n-aire, en utilisant des listes Clojure, avec la structure suivante.
Un nœud qui n'est pas une feuille est une liste en deux parties: la première partie est un élément représentant la racine de cette section de l'arbre; la seconde partie est un n éléments représentant des branches à partir de la racine. Les feuilles sont des listes ayant un mot-clé comme seul élément. Ainsi, je représente un arbre du formulaire,
(defn subt
[trees]
(let [subtree #(if (keyword? (first %)) (rest %) nil)
leaf? #(and (list %) (keyword? (first %)) (= (count %) 1))
sub (subtree trees)]
(if (every? leaf? sub)
nil
(cons (map subt sub) trees))))
avec la liste suivante:
(defn subtrees
[tree]
(loop [trees tree
results '()]
(if (empty? trees)
results
(let [subtree #(if (keyword? (first %)) (rest %) nil)
leaf? #(and (list %) (keyword? (first %)) (= (count %) 1))
sub (subtree (first trees))]
(if (every? leaf? sub)
(recur (rest trees) (into results sub))
(recur (into (rest trees) sub) (into results sub)))))))
Solution utilisant Récursivité
Je veux lister chaque sous-arbre propre d'un arbre donné. Je sais comment faire cela en utilisant la récursivité, comme suit:
(:A (:B (:C)) (:D))
Je fais donc le travail avec les arbres et résultats : Je commence par l'arborescence des arbres , puis j'ajoute chaque sous-arbre qui n'est pas une ou plusieurs feuilles dans les arbres et résultats à chaque étape ( ou: juste dans les résultats si j'ai une ou plusieurs feuilles). Cela me donne une liste de tous les sous-arbres appropriés de tree , qui est le point de la fonction. Voici la solution de travail avec des commentaires très détaillés et un tas de cas de test.
Ma question
Je voudrais savoir comment accomplir la même chose en utilisant des fonctions d'ordre supérieur. Ce que j'aimerais vraiment faire, c'est utiliser map et appeler la fonction de manière récursive: à chaque étape, il suffit d'appeler subtree sur chaque élément de la liste. Le problème que j'ai rencontré est que lorsque je fais cela, je me retrouve avec un énorme désordre de parenthèses et je ne peux pas toujours explorer le désordre pour accéder aux sous-arbres. Quelque chose comme ceci:
B -- C / A \ D
Vous pouvez voir que le (map subt sub) est ce que je cherche ici, mais je rencontre un beaucoup de difficulté à utiliser map , même si je pense que c'est ce que je veux pour ma fonction d'ordre supérieur. J'ai pensé à utiliser réduire comme substitut de la boucle dans les sous-arbres ci-dessus; mais parce que les arbres changent par l'ajout de sous-arbres, je ne pense pas que réduire soit approprié, du moins avec la boucle telle que je l'ai construite. Je dois dire aussi que je ne suis pas intéressé par une bibliothèque pour faire le travail; Je veux savoir comment le résoudre à l'aide des fonctions de base. Merci d'avance.
4 Réponses :
Vous pouvez accomplir avec la fonction walk-with-parents-readonly de le Tupelo bibliothèque . Voici le code:
-------------------------------------- Clojure 1.10.2-alpha1 Java 14 -------------------------------------- Testing tst.demo.core [(first item) levels] => [:com 0] [(first item) levels] => [:b 1] [(first item) levels] => [:g 2] [(first item) levels] => [:h 3] [(first item) levels] => [:c 2] [(first item) levels] => [:d 3] [(first item) levels] => [:i 4] [(first item) levels] => [:e 4] [(first item) levels] => [:f 5] [(first item) levels] => [:j 5] [(first item) levels] => [:k 6] [(first item) levels] => [:l 7] (clojure.core/deref sum) => 42
avec résultat
(ns tst.demo.core
(:use tupelo.test)
(:require [tupelo.core :as t]))
(def orbits
[:com
[:b
[:g
[:h]]
[:c
[:d
[:i]
[:e
[:f]
[:j
[:k
[:l]]]]]]]])
(def sum (atom 0))
(defn parent-levels
[parents]
(t/it-> parents
(count it)
(/ it 2)))
(defn count-orbits
[data]
(t/walk-with-parents-readonly data
{:enter (fn [parents item]
(when (vector? item)
(let [levels (parent-levels parents)]
(t/spyx [(first item) levels])
(swap! sum + levels))))}))
(dotest
(count-orbits orbits)
(t/spyx @sum))
Vous pouvez voir la documentation ici . Le code source montre comment l'implémenter a> (pourrait être simplifié pour un cas d'utilisation spécifique).
Merci; J'apprécie vraiment cela. Je cherche spécifiquement à faire cela sans bibliothèques supplémentaires, mais plutôt en utilisant les fonctions de base. (Cette exigence se trouve sur la dernière ligne de la question initiale; j'aurais dû trouver un moyen de la mettre en évidence.)
Voir le code source (lien ajouté ci-dessus). L'idée de base est qu'à chaque récursivité, vous ajoutez le vecteur parents à l'élément courant. Ensuite, vous comptez la longueur des parents vec et les additionnez pour obtenir le total.
Merci. J'ai l'idée de base; mais cela utilise pour dans la source. Ce que je voudrais savoir, ce sont les détails sur la façon de le faire en utilisant une fonction d'ordre supérieur.
map et for appliquent tous deux une fonction à chaque élément d'une collection. Vous pouvez facilement remplacer l'un par l'autre. Je pense que for est plus facile à lire dans la plupart des cas, car il est plus étalé, avec la fonction à la fin au lieu du milieu du formulaire. De plus, for donne un nom explicite à la variable de boucle, alors que map ne le fait normalement pas.
Oui; Je veux dire, je sais utiliser map et pour . Les idées de base ne sont pas difficiles. Le problème que j'ai est de gérer le grand nombre de parenthèses qui nuisent au résultat lorsque j'utilise des fonctions d'ordre supérieur. Il semble y avoir trop de cas individuels dont les résultats présentent des formats légèrement différents.
N'essayez pas de le faire dans une seule expression hautement imbriquée. Créez un tas de fonctions d'assistance courtes pour qu'il n'obtienne jamais plus de 2 niveaux d'imbrication.
Je me trompe peut-être, mais il semble que la fonction tree-seq de la bibliothèque principale devrait faire l'affaire pour vous:
(defn solve [data]
(let [items (clojure.string/split data #"\)|\s+")
pairs (partition 2 items)
lookup (reduce (fn [acc [par ch]] (assoc acc ch par)) {} pairs)
count-parents #(->> %
(iterate lookup)
(take-while identity)
count
dec)]
(apply + (map count-parents (distinct items)))))
(def data "COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L")
#'user/data
user> (solve data)
;;=> 42
user> (solve (slurp "./orb.txt"))
;;=> 402879 ;; for my task input data
il vous suffit d'exclure le premier élément, étant l'arbre lui-même.
Je sais, ce n'est pas la réponse à "comment écrire ce code manuellement",
mais l'analyse du code source de tree-seq devrait clarifier comment le faire de manière idiomatique dans clojure.
en fait, il utilise quelque chose comme ça (simplifié):
(defn my-tree-seq [data] (lazy-seq (cons data (mapcat my-tree-seq (rest data)))))
celui-ci est paresseux, il ne conduit donc pas à un débordement de pile malgré l'utilisation de la récursivité. Je ne pense pas vraiment qu'il faille optimiser davantage, mais dans un souci d'éducation.
qu'en est-il de la tâche elle-même, je la simplifierais d'une manière ou d'une autre, car vous n'avez pas vraiment besoin seulement besoin que les parents de chaque article comptent. Ainsi, vous n'avez même pas besoin de créer un arbre, juste la table de recherche enfant-> parent. Je peux penser à quelque chose comme ceci:
(tree-seq seq rest '(:A (:B (:C)) (:D))) ;;=> ((:A (:B (:C)) (:D)) (:B (:C)) (:C) (:D))
celui-ci pourrait être encore optimisé avec une programmation dynamique, mais pour les entrées fournies, il est assez bon.
Le tree-seq fait ce que je recherche; Merci. Et vous avez raison - il provient de la bibliothèque principale. Mais, comme vous l’avez compris, je cherche comment le faire manuellement. Ce n'est pas que je n'apprécie pas votre réponse; cela correspond à ma question. Mais la réponse de Rulle correspond davantage à ce que je recherchais en termes d'approche «manuelle».
@CuriousYogurt merci pour les commentaires! De plus, my-tree-seq est le clojure le plus idiomatique auquel je puisse même penser. (C'est pourquoi la bibliothèque principale utilise cette approche exacte)))
Voici une tentative de calcul de tous les sous-arbres en utilisant diverses fonctions de la bibliothèque standard.
(all-subtrees '(:A (:B (:C)) (:D)))
;; => #{(:D) (:B (:C)) (:C) (:A (:B (:C)) (:D))}
et nous pouvons l'appeler comme ceci:
(defn expand-subtrees [tree-set]
(into #{} (comp (map rest) cat) tree-set))
(defn all-subtrees [tree]
(reduce into #{}
(take-while seq (iterate expand-subtrees #{tree}))))
Une question de suivi: est-il idiomatique dans Clojure de garder la fonction d'assistance expand-subtrees séparée? Ou serait-il plus courant de l'intégrer à la fonction all-subtrees ?
notez que cette solution ne collecte que des sous-arborescences uniques . Bien que cela fonctionne toujours pour l'entrée de la tâche, il n'obtient pas vraiment tous les sous-arbres comme son nom l'indique.
aussi, (complément vide?) est juste seq . La documentation dit "Veuillez utiliser l'idiome (seq x) plutôt que (pas (vide? X))"
@CuriousYogurt Je pense qu'elle est plus lisible en tant que fonction séparée car (i) il est évident qu'elle calcule son résultat à partir d'une seule valeur et de rien capturé de la portée environnante et (ii) cela rend tous les sous-arbres plus lisible avec moins d'encombrement. @leetwinski Si deux sous-arbres correspondent au même élément d'ensemble, cela signifie qu'ils sont valeurs égales . Nous allons donc collecter tous les sous-arbres, juste que certains sous-arbres peuvent exister à de nombreux endroits de l'arbre. Vous pouvez facilement remplacer # {} par [] pour collecter les sous-arbres à partir d'une traversée en largeur d'abord si vous le souhaitez.
Commençons par une solution d'esprit similaire à celle de Rulle, mais en améliorant celle-ci:
(defn tree-seq-bf [branch? children node]
(let [children #(if (branch? %) (children %))]
(->> node
list
(iterate (partial mapcat children))
(take-while seq)
(apply concat))))
(defn tree-seq-df [branch? children node]
(let [children #(if (branch? %) (children %))]
(->> node
list
(iterate #(concat (children (first %)) (rest %)))
(take-while seq)
(map first))))
Notez que les sous-arbres sont produits paresseusement et dans le premier ordre. Pour les produire en profondeur d'abord (comme dans la solution de leetwinski mais en utilisant itérer et en évitant la récursivité), nous pouvons écrire:
(defn subtrees-bf [tree]
(->> tree
rest ; or list
(iterate (partial mapcat rest))
(take-while seq)
(apply concat)))
(defn subtrees-df [tree]
(->> tree
rest ; or list
(iterate #(concat (rest (first %)) (rest %)))
(take-while seq)
(map first)))
J'ai écrit ces fonctions dans le style sans point, ce que Clojure (comme la plupart des LISP) ne facilite pas, certaines des principales causes étant:
Deux autres versions idiomatiques / compréhensibles pourraient être:
(def subtrees-df
(comp
(partial map first)
(partial take-while seq)
(partial iterate
(comp
(partial apply concat)
(juxt (comp rest first) rest)))
rest)) ; replace this with list to include the original tree
Et maintenant généralisons ces approches et réécrivons tree-seq :
(def subtrees-bf
(comp
(partial apply concat)
(partial take-while seq)
(partial iterate (partial mapcat rest))
rest)) ; replace this with list to include the original tree