1
\$\begingroup\$

I've been playing around with functional programming for a while now and just started learning Clojure. So the problem I'm trying to solve is the following:

I have a tree-like hashmap of tasks where each task can include a number of tasks and each of those can include other tasks. The toy one I'm using for starters looks like this:

(def master-list
  {:name "Master List"
   :details "One List to Rule them all"
   :list
   [{:name "Writing"
     :details "Writing things is fun"
     :list
     [{:name "Write A Best-Seller"
       :details "Making money is also fun"
       :list
       [{:name "Come up with the plot"
         :details "What do I want to talk about?"}]}
      {:name "Write for the New York Times"
       :details "People need to hear this"}]}
    {:name "Reading"
     :details "I have a long list of books to read"
     :list
     [{:name "The Catcher in the Rye"
       :details "Who is Holden Caulfield and Why should I care?"}]}
    {:name "Profit"
     :details "All Done"}]})

Where :list contain the subtask list of a given task. Ok, cool, so far so good.

But in order to work with a given task I need to be able to get to it within that hashmap. And because that hashmap sits within an atom and to keep every representation of the tasks consistent I can't just copy it into a new map. What I figured is that I'd keep a vector of keys that can be used to access each item individually with the function get-in.

For example to refer to the task named "Come up with the plot" I can just store the vector [:list 0 :list 0 :list 0]. Since

(get-in master-list [:list 0 :list 0 :list 0])

Will return me the task I need. Cool.

So now I can access a task within the hashmap and if that changes the changes will be reflected everywhere. Now I need to have a way to find that vector given any of my tasks. Something that will always pass the test (called find-in in the code below):

(= list-i-have (get-in master-list (helper/find-in master-list list-i-have)))
;;Should always be true

After a while, I came up with the code:

(defn- inner-func [index item]
  (cond
   (= item '()) nil
   (seq? item) (conj item index)
   (== item true) (conj '() index)
   true nil))

(defn- is-in [task subtask]
  (cond
   (= task subtask) true
   (:list task)  (flatten (keep-indexed inner-func (keep #(is-in % subtask) (:list task))))
   true  nil))

(defn find-in [task subtask]
  (let [result (is-in task subtask)]
    (cond
     (== result true)  []
     (= result '())   nil
     true (interleave (cycle [:list]) result))))

That seems to solve my problem which brings me to my (many) questions:

  1. What do you think about the design choices?
  2. Have I missed any other ways to represent the list and the selected part of the list? Can you find any major flaws with my choice?
  3. What about the code itself? Is it functional? As I was writing it, I felt like I kept falling back to imperative-like solutions.
  4. Any other problems with it I might have missed?
\$\endgroup\$
2
\$\begingroup\$

I think your choice of using a nested map/vector structure is a good one, and I think it is pretty idiomatic to Clojure. It can be tricky to work with nested structures like this, but it's certainly doable.

Your find-in function (and the private functions it depend on) is an imperative kind of solution -- you're iterating through the maps/lists and building up a "key vector" from scratch. I'm not sure if there is a strictly non-imperative way to navigate tree structures like this, but there is at least a much simpler way. You should have a look at clojure.zip. It provides zippers, which are data structures that represent a location in a tree-like data structure, and they keep track of the path that it took to get there.

With zippers, the approach to representing the "location of" (or "path to") an item is a bit different. To use your example:

(get-in master-list [:list 0 :list 0 :list 0])

This returns the node {:name "Come up with the plot" :details "What do I want to talk about?"}. In zipper terminology, this is "down down down" -- if you visualize the tree in your mind, with the master list as the root, you go down and end up at the first item in the list ("Writing"), then down again to the first item of that list ("Write A Best-Seller"), and then down a third time to the first item of that list, which is "Come up with the plot." Here's how you would code that:

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

; (def master-list
;   ...)

(def zipper-list (z/zipper map? :list #(assoc %1 :list %2) master-list))

(-> zipper-list z/down z/down z/down z/node)

Zippers can be confusing at first, so I'll explain how this one works. The function clojure.zip/zipper takes 4 arguments:

  1. A function that, given a node in the tree, returns true if that node can have children, even if it currently doesn't. I used map? because each node we're working with is a map that can potentially have a :list field, containing children.

  2. A function that, given a branch node, returns a seq of its children. In this case, we can use :list as a function to get a given node's children (in Clojure, a keyword can be used as a function to look itself up in a map).

  3. A function that takes two arguments -- (1) an existing node and (2) a seq of children -- and returns a new branch node that has the supplied children. In our case, the function would be #(assoc %1 :list %2).

  4. The actual structure that we're navigating; in this case, it's master-list.

Now you can pass the zipper through any of clojure.zip's handy methods for navigating zippers. Once you've reached the node you want, you can use the clojure.zip/node method to return the actual data in the node.


I'm not sure what your use case is, but it sounds like you might want to have a way of representing an "address of" or "path to" a certain node. Working with zippers, you could actually represent a node's location as a list of the zipper functions necessary to reach it, something like this:

(def come-up-with-a-plot [z/down z/down z/down])

And then if you wanted to, you could write a helper function that inserts the zipper and the directions into a form just like we used above, sandwiched between -> and z/node:

(defn get-node [zipper directions]
  (eval `(-> ~zipper ~@directions z/node)))

(get-node zipper-list [z/down z/down z/down])

As an alternative, you could use a nested map structure that has only maps, no vectors, and use the names of each node as their keys:

(def master-list
   {:details "One List to Rule them all"
    "Writing"
      {:details "Writing things is fun"
      "Write A Best-Seller"
        {:details "Making money is also fun"
         "Come up with the plot"
           {:details "What do I want to talk about?"}}
      "Write for the New York Times"
      {:details "People need to hear this"}}
    "Reading"
      {:details "I have a long list of books to read"
       "The Catcher in the Rye"
         {:details "Who is Holden Caulfield and Why should I care?"}}
    "Profit"
      {:details "All Done"}})

This way, you would access each node using the exact names of each node in the tree in string form, like this:

(get-in master-list ["Writing" "Write A Best-Seller" "Come up with the plot"])

The obvious downside of this method is that it's vulnerable to accidental variation in the string keys. You might accidentally type, say, "Come up with a plot," and get nil as a result because the map doesn't have that key. Another downside is that maps aren't ordered or sorted, so any items that you add in (say by using assoc) are not stored in any particular order; although, you could remedy this by using ordered lists.

If you want my 2 cents, I think zippers are the best way to go for something like this. :)

\$\endgroup\$

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.