(defn tester [tests]
  (doseq [test tests]
    (mif ['(?id -- ?pre => ?post) test]
      (if-not (= (eval (? pre)) (? post))
        (mout '(?id -- ?pre => ?post)))
      `(error ill formed test: ~test)
      )))

(def tree-tests
  '( (1 -- (in-tree? 'x '(a (b c x) (d e f) g)) => true)
     (2 -- (in-tree? 'y '(a (b c x) (d e f) g)) => false)
     (3 -- (in-tree? 'x ()) => false)
     (4 -- (in-tree? () '(a (b c x) (d e f) g)) => false)
     (5 -- (in-tree? 'x '(x a b c)) => true)
     (6 -- (in-tree? 'x '(a x b c)) => true)
     (7 -- (in-tree? 'x '(((x a) b c))) => true)
     ))


=====


;=======================================================================================
; lecture trace 4 -- recursive trees
;=======================================================================================

; simple case, non-optimised recursion
;--------------------------------------

(defn find-atom [lis val]
  (cond
    (empty? lis)
    false

    (= (first lis) val)
    true

    :else
    (find-atom (rest lis) val)
    ))

> (find-atom '(the cat sat on the mat) 'sat)
true

> (find-atom '(the cat sat on the mat) 'armadillo)
false


;
; or...
; still simple case but using recur
;-------------------------------------

(defn find-atom [lis val]
  (cond
    (empty? lis)
    false

    (= (first lis) val)
    true

    :else
    (recur (rest lis) val)
    ))


> (find-atom '(the cat sat on the mat) 'sat)
true

> (find-atom '(the cat sat on the mat) 'armadillo)
false


; a tree example, first attempt
;--------------------------------

(def nested1 '(a ((b) c) (d (e (f g) h) i)))

(defn find-atom [lis val]
  (cond
    (empty? lis)
    false

    (= (first lis) val)
    true

    (seq? (first lis))
    (or (find-atom (first lis) val)
      (recur (rest lis) val))

    :else
    (recur (rest lis) val)
    ))


> (find-atom nested1 'c)
true

> (find-atom nested1 'cat)
false


; another tree example, thinking trees this time
;-----------------------------------------------

(defn find-atom [tree val]
  (cond
    (= tree val) true

    (and (seq? tree) (not (empty? tree)))
    (or (find-atom (first tree) val)
        (recur (rest tree) val))

    :else false
    ))


user=> (find-atom nested1 'c)
true
user=> (find-atom nested1 'cat)
false


; may be better to use a helper...
(defn tree? [t]
  (and (seq? t) (not (empty? t))))


; another variation
;-----------------------------------------------

;think about...

(or nil false :else 'kipper 'cod)
(and 'kipper 'cod 'carp :else false)
(and 'kipper 'cod 'carp :else nil)
(and 'kipper 'cod 'carp :else 'banana)



(defn findx [tree x]
  (or (= x tree)
    (when (tree? tree)
      (or (findx (first tree) x)
          (findx (rest tree) x))
      )))


user=> (trace-vars findx)
#'user/findx
user=> (findx nested1 'd)
TRACE t310: (user/findx (a ((b) c) (d (e (f g) h) i)) d)
TRACE t311: | (user/findx a d)
TRACE t311: | => nil
TRACE t312: | (user/findx (((b) c) (d (e (f g) h) i)) d)
TRACE t313: | | (user/findx ((b) c) d)
TRACE t314: | | | (user/findx (b) d)
TRACE t315: | | | | (user/findx b d)
TRACE t315: | | | | => nil
TRACE t316: | | | | (user/findx () d)
TRACE t316: | | | | => nil
TRACE t314: | | | => nil
TRACE t317: | | | (user/findx (c) d)
TRACE t318: | | | | (user/findx c d)
TRACE t318: | | | | => nil
TRACE t319: | | | | (user/findx () d)
TRACE t319: | | | | => nil
TRACE t317: | | | => nil
TRACE t313: | | => nil
TRACE t320: | | (user/findx ((d (e (f g) h) i)) d)
TRACE t321: | | | (user/findx (d (e (f g) h) i) d)
TRACE t322: | | | | (user/findx d d)
TRACE t322: | | | | => true
TRACE t321: | | | => true
TRACE t320: | | => true
TRACE t312: | => true
TRACE t310: => true
true


; sum-tree - a few variations
;-----------------------------------------------

(defn sum-tree [tree]
  (cond
    (number? tree) tree

    (tree? tree)
    (+ (sum-tree (first tree))
       (sum-tree (rest tree)))

    :else 0
    ))

(def nums1 '(1 ((2) 3) (4 (5 (6 7) 8) 9)))

user=> (sum-tree nums1)
45


(def nums2 '(1 ((2) 3) 4))

user=> (sum-tree nums2)
TRACE t1135: (user/sum-tree (1 ((2) 3) 4))
TRACE t1136: | (user/sum-tree 1)
TRACE t1136: | => 1
TRACE t1137: | (user/sum-tree (((2) 3) 4))
TRACE t1138: | | (user/sum-tree ((2) 3))
TRACE t1139: | | | (user/sum-tree (2))
TRACE t1140: | | | | (user/sum-tree 2)
TRACE t1140: | | | | => 2
TRACE t1141: | | | | (user/sum-tree ())
TRACE t1141: | | | | => 0
TRACE t1139: | | | => 2
TRACE t1142: | | | (user/sum-tree (3))
TRACE t1143: | | | | (user/sum-tree 3)
TRACE t1143: | | | | => 3
TRACE t1144: | | | | (user/sum-tree ())
TRACE t1144: | | | | => 0
TRACE t1142: | | | => 3
TRACE t1138: | | => 5
TRACE t1145: | | (user/sum-tree (4))
TRACE t1146: | | | (user/sum-tree 4)
TRACE t1146: | | | => 4
TRACE t1147: | | | (user/sum-tree ())
TRACE t1147: | | | => 0
TRACE t1145: | | => 4
TRACE t1137: | => 9
TRACE t1135: => 10
10


(defn sum-tree2
  ([tree] (sum-tree2 tree 0))
  ([tree n]
    (cond
      (number? tree) (+ tree n)

      (tree? tree)
      (sum-tree2 (rest tree) (+ n (sum-tree2 (first tree))))

      :else n
      )))

user=> (sum-tree2 nums1)
45

user=> (trace-vars sum-tree2)
#'user/sum-tree2
user=> (sum-tree2 nums2)
TRACE t1152: (user/sum-tree2 (1 ((2) 3) 4))
TRACE t1153: | (user/sum-tree2 (1 ((2) 3) 4) 0)
TRACE t1154: | | (user/sum-tree2 1)
TRACE t1155: | | | (user/sum-tree2 1 0)
TRACE t1155: | | | => 1
TRACE t1154: | | => 1
TRACE t1156: | | (user/sum-tree2 (((2) 3) 4) 1)
TRACE t1157: | | | (user/sum-tree2 ((2) 3))
TRACE t1158: | | | | (user/sum-tree2 ((2) 3) 0)
TRACE t1159: | | | | | (user/sum-tree2 (2))
TRACE t1160: | | | | | | (user/sum-tree2 (2) 0)
TRACE t1161: | | | | | | | (user/sum-tree2 2)
TRACE t1162: | | | | | | | | (user/sum-tree2 2 0)
TRACE t1162: | | | | | | | | => 2
TRACE t1161: | | | | | | | => 2
TRACE t1163: | | | | | | | (user/sum-tree2 () 2)
TRACE t1163: | | | | | | | => 2
TRACE t1160: | | | | | | => 2
TRACE t1159: | | | | | => 2
TRACE t1164: | | | | | (user/sum-tree2 (3) 2)
TRACE t1165: | | | | | | (user/sum-tree2 3)
TRACE t1166: | | | | | | | (user/sum-tree2 3 0)
TRACE t1166: | | | | | | | => 3
TRACE t1165: | | | | | | => 3
TRACE t1167: | | | | | | (user/sum-tree2 () 5)
TRACE t1167: | | | | | | => 5
TRACE t1164: | | | | | => 5
TRACE t1158: | | | | => 5
TRACE t1157: | | | => 5
TRACE t1168: | | | (user/sum-tree2 (4) 6)
TRACE t1169: | | | | (user/sum-tree2 4)
TRACE t1170: | | | | | (user/sum-tree2 4 0)
TRACE t1170: | | | | | => 4
TRACE t1169: | | | | => 4
TRACE t1171: | | | | (user/sum-tree2 () 10)
TRACE t1171: | | | | => 10
TRACE t1168: | | | => 10
TRACE t1156: | | => 10
TRACE t1153: | => 10
TRACE t1152: => 10
10



(defn sum-tree3
  ([tree] (sum-tree3 tree 0))
  ([tree n]
    (cond
      (number? tree) (+ tree n)

      (tree? tree)
      (sum-tree3 (rest tree) (sum-tree3 (first tree) n))

      :else n
      )))


user=> (sum-tree3 nums1)
45

user=> (trace-vars sum-tree3)
#'user/sum-tree3
user=> (sum-tree3 nums2)
TRACE t1177: (user/sum-tree3 (1 ((2) 3) 4))
TRACE t1178: | (user/sum-tree3 (1 ((2) 3) 4) 0)
TRACE t1179: | | (user/sum-tree3 1 0)
TRACE t1179: | | => 1
TRACE t1180: | | (user/sum-tree3 (((2) 3) 4) 1)
TRACE t1181: | | | (user/sum-tree3 ((2) 3) 1)
TRACE t1182: | | | | (user/sum-tree3 (2) 1)
TRACE t1183: | | | | | (user/sum-tree3 2 1)
TRACE t1183: | | | | | => 3
TRACE t1184: | | | | | (user/sum-tree3 () 3)
TRACE t1184: | | | | | => 3
TRACE t1182: | | | | => 3
TRACE t1185: | | | | (user/sum-tree3 (3) 3)
TRACE t1186: | | | | | (user/sum-tree3 3 3)
TRACE t1186: | | | | | => 6
TRACE t1187: | | | | | (user/sum-tree3 () 6)
TRACE t1187: | | | | | => 6
TRACE t1185: | | | | => 6
TRACE t1181: | | | => 6
TRACE t1188: | | | (user/sum-tree3 (4) 6)
TRACE t1189: | | | | (user/sum-tree3 4 6)
TRACE t1189: | | | | => 10
TRACE t1190: | | | | (user/sum-tree3 () 10)
TRACE t1190: | | | | => 10
TRACE t1188: | | | => 10
TRACE t1180: | | => 10
TRACE t1178: | => 10
TRACE t1177: => 10
10



(defn sum-tree [tree]
  (cond
    (number? tree)  tree
    (empty?  tree)  0
    :else
    (reduce + (map sum-tree tree))
    ))

user=> (sum-tree '(1 2 (3 (4 5) 6 7) ((8 (9)))))
45


(defn sum-tree [tree]
  (reduce + (flatten tree)))

user=> (sum-tree '(1 2 (3 (4 5) 6 7) ((8 (9)))))
45



; inc-tree needs to build a result
;-----------------------------------------------

(defn inc-tree [tree]
  (cond
    (number? tree)  (inc tree)
    (empty? tree)   tree

    :else
    (cons (inc-tree (first tree)) (inc-tree (rest tree)))
    ))


user=> (inc-tree '(1 2 (3 (4 5) 6 7) ((8 (9)))))
(2 3 (4 (5 6) 7 8) ((9 (10))))




(defn sum-tree [tree]
  (cond
    (number? tree)  tree
    (empty?  tree)  0
    :else
    (+ (sum-tree (first tree)) (sum-tree (rest tree)))
    ))

user=> (sum-tree '(1 2 (3 (4 5) 6 7) ((8 (9)))))
45


(defn sum-tree [tree]
  (cond
    (number? tree)  tree
    (empty?  tree)  0
    :else
    (reduce + (map sum-tree tree))
    ))

user=> (sum-tree '(1 2 (3 (4 5) 6 7) ((8 (9)))))
45



; depth 1st search dynamically constructs a tree
;-----------------------------------------------

(defn depth-search
  [state goal path limit lmg]
  (cond
    (= state goal)  (conj path state)
    (<= limit 0)    false
    :else
    (some (fn [s] (depth-search s goal (conj path state) (dec limit) lmg))
       (lmg state))
    ))

(defn num-lmg [n]
  (list (* n 2) (- n 3) (+ n 1)))


user=> (depth-search 12 33 nil 10 num-lmg)
(33 36 39 42 45 48 24 12)

user=> (time (depth-search 12 33 nil 20 num-lmg))
"Elapsed time: 69307.539707 msecs"
(33 36 39 42 45 48 51 54 57 60 63 66 69 72 36 39 42 45 48 24 12)


;;; TREE EXPANSION

;===========================
; grammar expansion
;===========================

(def grammar
  '{s (np vp)
    np (det n)
    vp (v np)
    })

(def lex
  '{det (the a every one)
    n   (cat dog rat frog)
    v   (ate chased danced-with)
    })

(defn expand [src]
  (if (empty? src) src
     (let [[f & r] src]
        (if (f grammar)
           (expand (concat (f grammar) r))
           (cons (rand-nth (f lex)) (expand r)))
         )))

user=> (expand '[s])
(every dog danced-with a frog)
user=> (expand '[s])
(a cat chased a rat)
user=> (expand '[s])
(every frog chased every cat)