4
\$\begingroup\$

A program that I work on constantly updates and modifies program state containing an arbitrarily deep and wide tree. The data looks something like this.

(defonce state
         (r/atom {:some  "program"
                  :state "here"
                  :tree  [{:topic    "Books"
                           :expanded true
                           :children [{:topic "Titles"}
                                      {:topic    "Authors"
                                       :expanded true
                                       :children [{:topic "Alice"}
                                                  {:topic "Bob"}
                                                  {:topic "Carol"}]}
                                      {:topic "Genres"}]}
                          {:topic    "CDs"
                           :children [{:topic "Genres"}
                                      {:topic "Albums"}
                                      {:topic "Artists"}]}
                          {:topic    "To Do"
                           :expanded true
                           :children [{:topic    "Spouse Birthday"
                                       :expanded nil
                                       :due-date "07/31/2025"
                                       :children [{:topic "Buy Card"}
                                                  {:topic "Buy Jewelry"}
                                                  {:topic "Buy Cake"}]}]}]}))

As the program runs, I need to extract the series of numeric vector indices to reach the visible topics (those that have :children where the :expanded flag is present and "truthy").

Here is a method that works.

;; This flattening function is from an idea presented in response to
;; this question:
;; https://stackoverflow.com/questions/5232350/clojure-semi-flattening-a-nested-sequence
(defn flatten-to-vectors
  [s]
  (mapcat #(if (every? coll? %) (flatten-to-vectors %) (list %)) s))

(defn visible-nodes
  [tree so-far]
  (flatten-to-vectors
    (map-indexed
      (fn [idx ele]
        (let [new-id (conj so-far idx)]
          (if (not (and (:children ele) (:expanded ele)))
            new-id
            (cons new-id (visible-nodes (:children ele) new-id)))))
      tree)))

;; The function can be called like this on the data above.
(println (visible-nodes (:tree @state) []))
;; => ([0] [0 0] [0 1] [0 1 0] [0 1 1] [0 1 2] [0 2] [1] [2] [2 0])

Although this works, it seems like I should be able to generate the correct result without creating nested sequences that require flattening. But I just can't come up with anything.

Any suggestions would be appreciated.

\$\endgroup\$

migrated from stackoverflow.com Apr 26 at 1:02

This question came from our site for professional and enthusiast programmers.

3
\$\begingroup\$

You are right to want to avoid creating the nested structure to begin with. I imagine you read my answer in the question you linked (the second one). As there, here the solution is to use mapcat instead of map. And as I also say in the comments there, while mapcat-indexed does not exist, you can just pass an extra (range) argument to get numbering.

(defn visible-nodes [tree]
  (mapcat (fn [idx ele]
            (map #(cons idx %)
                 (cons []
                       (when (:expanded ele)
                         (visible-nodes (:children ele))))))
          (range), tree))
\$\endgroup\$
  • \$\begingroup\$ Thanks for this. It works. You are right; I did read your comments on the other question I linked to. That's what prompted me to look for a better solution. I tried using mapcat and adding the (range) argument with variations of the original function, but could not manage to come up with something that worked. \$\endgroup\$ – clartaq Apr 26 at 21:45
2
\$\begingroup\$

Depending on your final goal, you may be interested in the Tupelo Forest library. Here is a sample of what you can do (data converted to the "tree" format):

(dotest-focus
  (with-forest (new-forest)
    (let [data          {:tag      "program"
                         :state    "here"
                         ::tf/kids [{:topic    "Books"
                                     :expanded true
                                     ::tf/kids [{:topic "Titles" ::tf/kids []}
                                                {:topic    "Authors"
                                                 :expanded true
                                                 ::tf/kids [{:topic "Alice" ::tf/kids []}
                                                            {:topic "Bob" ::tf/kids []}
                                                            {:topic "Carol" ::tf/kids []}]}
                                                {:topic "Genres" ::tf/kids []}]}
                                    {:topic    "CDs"
                                     ::tf/kids [{:topic "Genres" ::tf/kids []}
                                                {:topic "Albums" ::tf/kids []}
                                                {:topic "Artists" ::tf/kids []}]}
                                    {:topic    "To Do"
                                     :expanded true
                                     ::tf/kids [{:topic    "Spouse Birthday"
                                                 :expanded nil
                                                 :due-date "07/31/2025"
                                                 ::tf/kids [{:topic "Buy Card" ::tf/kids []}
                                                            {:topic "Buy Jewelry" ::tf/kids []}
                                                            {:topic "Buy Cake" ::tf/kids []}]}]}]}

processing:

          root-hid      (add-tree data)
          expanded-hids (find-hids root-hid [:** {:expanded true}])
          ]
      (spy-pretty (hid->bush root-hid))
      (doseq [hid expanded-hids]
        (newline)
        (println "-----------------------------------------------------------------------------")
        (spy-pretty :node (hid->node hid))
        (spy-pretty :bush (hid->bush hid)))
      )
    )
  )

with results, overall data in "bush" format:

[{:tag "program", :state "here"}
 [{:topic "Books", :expanded true}
  [{:topic "Titles"}]
  [{:topic "Authors", :expanded true}
   [{:topic "Alice"}]
   [{:topic "Bob"}]
   [{:topic "Carol"}]]
  [{:topic "Genres"}]]
 [{:topic "CDs"}
  [{:topic "Genres"}]
  [{:topic "Albums"}]
  [{:topic "Artists"}]]
 [{:topic "To Do", :expanded true}
  [{:topic "Spouse Birthday", :expanded nil, :due-date "07/31/2025"}
   [{:topic "Buy Card"}]
   [{:topic "Buy Jewelry"}]
   [{:topic "Buy Cake"}]]]]

and the 3 nodes with a truthy value for :expanded as both a raw node or a "bush":

-----------------------------------------------------------------------------
 :node => 
{:tupelo.forest/khids [1001 1005 1006], :topic "Books", :expanded true}

 :bush => 
[{:topic "Books", :expanded true}
 [{:topic "Titles"}]
 [{:topic "Authors", :expanded true}
  [{:topic "Alice"}]
  [{:topic "Bob"}]
  [{:topic "Carol"}]]
 [{:topic "Genres"}]]

-----------------------------------------------------------------------------
 :node => 
{:tupelo.forest/khids [1002 1003 1004],
 :topic "Authors",
 :expanded true}

 :bush => 
[{:topic "Authors", :expanded true}
 [{:topic "Alice"}]
 [{:topic "Bob"}]
 [{:topic "Carol"}]]

-----------------------------------------------------------------------------
 :node => 
{:tupelo.forest/khids [1015], :topic "To Do", :expanded true}

 :bush => 
[{:topic "To Do", :expanded true}
 [{:topic "Spouse Birthday", :expanded nil, :due-date "07/31/2025"}
  [{:topic "Buy Card"}]
  [{:topic "Buy Jewelry"}]
  [{:topic "Buy Cake"}]]]
\$\endgroup\$
  • \$\begingroup\$ Did something happen to your code in the migration? The "processing" section looks cut off at the top. \$\endgroup\$ – amalloy Apr 26 at 1:39
  • \$\begingroup\$ It's OK, just a continuation of the let form above`. \$\endgroup\$ – Alan Thompson Apr 26 at 13:14
  • \$\begingroup\$ Thanks for pointing out this library. I had not heard of it. My needs are so simple though that I don't need the added dependency at this time. \$\endgroup\$ – clartaq Apr 26 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.