unit02trees.clj

(ns unit02.trees)


; Tree ------------------------------------------------------------------------
;
; A tree is equivalent to a single node.
; A node is basically a map:
;
; {:label :foo :children [... nodes ...]}

(defrecord Node [label children])

; Sample Tree -----------------------------------------------------------------
;
;     a
;  b     c
; d e   f g
(def sample (Node. :a [(Node. :b [(Node. :d [])
                                  (Node. :e [])])
                       (Node. :c [(Node. :f [])
                                  (Node. :g [])])]))

; Searches --------------------------------------------------------------------
(defn- search [frontier-conj tree goal]
  (loop [frontier (seq [[tree]])
         examined 1]
    (let [path (first frontier)
          current (last path)]
      (if (= (:label current) goal)
        {:path (map :label path)
         :examined examined}
        (recur (frontier-conj (rest frontier)
                              (map #(conj path %) (:children current)))
               (inc examined))))))


(defn- frontier-conj-depth [frontier children]
  (concat children frontier))

(defn- frontier-conj-breadth [frontier children]
  (concat frontier children))


(def search-depth (partial search frontier-conj-depth))
(def search-breadth (partial search frontier-conj-breadth))


; Scratch ---------------------------------------------------------------------
(search-depth sample :e)
(search-breadth sample :e)