My 2c:
Regarding learning how to model a complex data structure in a
functional paradigm:
I can think of few resources which sum up the proper mindset you
need to get into
better than the canonical Clojure essay on state and identity, found
here:
http://clojure.org/state
Regarding how to model a graph in Clojure:
I would suggest that you avoid thinking about refs unless you are
likely to need to
perform some kind of concurrent updates to your graph. A nested
associative data
structure should do the trick just fine.
(defrecord Node [foo bar baz])
(defn node [foo bar baz] (Node. foo bar baz))
(def the-graph {})
(defn add-node [g n]
(if (g n)
g
(assoc g n {:next #{} :prev #{}})))
(defn add-edge [g n1 n2]
(-> g
(add-node n1)
(add-node n2)
(update-in [n1 :next] conj n2)
(update-in [n2 :prev] conj n1)))
(defn remove-edge [g n1 n2]
(-> g
(add-node n1)
(add-node n2)
(update-in [n1 :next] disj n2)
(update-in [n2 :prev] disj n1)))
(defn remove-node [g n]
(if-let [{:keys [next prev]} (g n)]
((comp
#(dissoc % n)
#(reduce (fn [g* n*] (remove-edge g* n* n)) % prev)
#(reduce (fn [g* n*] (remove-edge g* n n*)) % next))
g)
g))
(defn contains-node? [g n]
(g n))
(defn contains-edge? [g n1 n2]
(get-in g [n1 :next n2]))
(defn next-nodes [g n]
(get-in g [n :next]))
;; Assumes DAG
(defn depth-first-search [g root-node goal?]
(loop [open-list (list root-node)]
(when-first [n open-list]
(if (goal? n)
n
(recur (concat (next-nodes g n) (rest open-list)))))))
And there you go. A fast, functional DAG implementation that doesn't
use any mutable state.
Happy hacking,
~Gary
On Jun 16, 10:08 am, Colin Yates <[email protected]> wrote:
> (newbie warning)
>
> Our current solution is an OO implementation in Groovy and Java. We
> have a (mutable) Project which has a DAG (directed acyclic graph).
> This is stored as a set of nodes and edges. There are multiple
> implementations of nodes (which may themselves be Projects). There
> are also multiple implementations of edges.
>
> My question isn't how to do this in a functional paradigm, my first
> question is *how do I learn* to do this in a functional paradigm. I
> want to be able to get the answer myself ;). To that end, are there
> any "domain driven design with functional programming" type resources?
>
> A more specific question is how do I model a graph? These graphs can
> be quite extensive, with mutations on the individual nodes as well as
> the structure (i.e. adding or removing branches). Does this mean that
> every every node would be a ref? I think the general answer is that
> the aggregate roots are refs, meaning they are an atomic block, but is
> there any more guidance?
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
