How can I generate a list from a nested map in Clojure?

Question

I have this atom:

(def test (atom {:james {:friends [:lucy :john :daisy]},
                 :lucy {:friends [:james :daisy]},
                 :daisy {:friends [:james :lucy]},
                 :john {:friends [:james]}}))

Giving :james as an argument, I need to iterate over its :friends and put every friend of :james friends in a list. The result must be something like this:

(:james :daisy :james :james :lucy)

This is my best effort so far:

(def user :james)

(def test2 (atom []))

(defn access
  [user]
  (get-in @test [user :friends]))

(doseq [connection (access user)]
  (swap! test2 concat (access connection)))

@test2

I don't think that using another atom (test2) is the most idiomatic way to do it.

Answer 1

Here's a way to solve the transitive friends-of-friends problem with core.logic and facts. First make a fact DB and db-rel for friendship:

(require '[clojure.core.logic :refer :all]
         '[clojure.core.logic.pldb :as pldb])

(def input
  {:james {:friends [:lucy :john :daisy]},
   :lucy  {:friends [:james :daisy]},
   :daisy {:friends [:james :lucy]},
   :john  {:friends [:james]}})

(pldb/db-rel friend p1 p2)

(def friends
  (apply pldb/db
    (for [[p1 {:keys [friends]}] input
          p2 friends]
      [friend p1 p2])))

Then write a function that takes a friend and binds the answer to the friends of all that friend's friends.

(defn friends-once-removed [f]
  (pldb/with-db friends
    (run* [q]
      (fresh [fs]
        (friend f fs)
        (friend fs q)))))

(friends-once-removed :james)
=> (:lucy :james :daisy :james :james)

Answer 2

A different way (or you call it 'indirect' way) to do this kind of query is through Datalog, where you first turn your nested map into facts:

(def friendship (mapcat (fn [[p {xs :friends}]]
                          (for [f xs]
                            [p :person/friend f]))
                        {:james {:friends [:lucy :john :daisy]},
                         :lucy  {:friends [:james :daisy]},
                         :daisy {:friends [:james :lucy]},
                         :john  {:friends [:james]}}))
;; =>
([:james :person/friend :lucy]
 [:james :person/friend :john]
 [:james :person/friend :daisy]
 [:lucy :person/friend :james]
 [:lucy :person/friend :daisy]
 [:daisy :person/friend :james]
 [:daisy :person/friend :lucy]
 [:john :person/friend :james])

then perform Datalog query on the facts with custom rules like friend and friend-of-friend. E.g. to find friend-of-friend of :james:

(d/q '[:find [?f ...]
       :where (friend-of-friend ?p ?f)
       :in $ ?p %]
     friendship
     :james
     '[[(friend ?p ?f)
        [?p :person/friend ?f]]
       [(friend-of-friend ?p ?f)
        (friend ?p ?x)
        (friend ?x ?f)
        [(not= ?p ?f)]]])
;; => [:daisy :lucy]

where

[:find [?f ...]
 :where (friend-of-friend ?p ?f)
 :in $ ?p %]

is the query, friendship is the facts and is mapped to $, :james is the subject of the query (mapped to argument ?p) and % is the rules defined as:

[[(friend ?p ?f)                        ; 1. What is a friend?
  [?p :person/friend ?f]]               ;   ?p has an attribute :person/friend defined with ?f
 [(friend-of-friend ?p ?f)              ; 2. Friend of friend
  (friend ?p ?x)                        ;   ?p and ?x are friends (base on #1)
  (friend ?x ?f)                        ;   ?x and ?f are friends
  [(not= ?p ?f)]]]                      ;   ?p and ?f not same person

Note: above example is using datascript

Answer 3

I'd only use atoms on the "outest level" of the whole application. They are storage for shareable, concurrently accessed, mutable, ... data (often global).

Write the functions you need the way that they are agnostic of such things as good as you can. It makes testing alot easier if you end up with pure functions. If you want to accumulate data then shape it; there is let to assing calcuation steps before returning etc.

So this is roughly the route i'd go (note, that there are may ways to skin a cat for concating your lists, I picked mapcat):

(defn user
  [users user-name]
  (get users user-name))

(defn friends
  [user]
  (get user :friends))

(defn user-friends
  [users user-name]
  (some->> user-name (user users) (friends)))

(defn friends-friends
  [users user-name]
  (when-let [friend-names (user-friends users user-name)]
    (mapcat (partial user-friends users) friend-names))) ; XXX replacement for the accumulating concat

And finally in your tests or REPL:

(let [users {:james {:friends [:lucy :john :daisy]}
             :lucy  {:friends [:james :daisy]}
             :daisy {:friends [:james :lucy]}
             :john  {:friends [:james]}}]
  (friends-friends users :james))
; => (:james :daisy :james :james :lucy)

Answer 4

True, you don't need an intermediate atom.

(def users (atom {:james {:friends [:lucy :john :daisy]},
                 :lucy   {:friends [:james :daisy]},
                 :daisy  {:friends [:james :lucy]},
                 :john   {:friends [:james]}}))

(defn friends [dict level users]
    (-> (fn [users] (mapcat #(get-in dict [% :friends]) users))
        (iterate users)
        (nth level)))

(friends @users 2 [:james])