(defstruct node :elt :l :r) (defn bst-insert [bst x comp] (if (nil? bst) (struct node x) (let [elt (:elt bst)] (if (= x elt) bst (if (comp x elt) (struct node elt (bst-insert (:l bst) x comp) (:r bst)) (struct node elt (:l bst) (bst-insert (:r bst) x comp)))))))

The function is non-destructive. Creating a BST can be done like this:

(def nums (reduce (fn [acc x] (bst-insert acc x <)) nil [5 8 4 2 1 9 6 7 3]))Obviously the function does not use a tail recursion. The value of the recursive call to

(defn bst-insert-tc [bst x comp] (loop [bst bst acc '()] (if (nil? bst) (loop [tree (struct node x) stack acc] (let [[lr elt branch] (first stack)] (if (empty? stack) tree (if (= lr :l) (recur (struct node elt branch tree) (rest stack)) (recur (struct node elt tree branch) (rest stack)))))) (let [elt (:elt bst)] (if (= x elt) bst (if (comp x elt) (recur (:l bst) (cons [:r elt (:r bst)] acc)) (recur (:r bst) (cons [:l elt (:l bst)] acc))))))))This approach works but is a bit naive and the second loop can be simplified by using reduce:

(defn bst-insert-tc2 [bst x comp] (loop [bst bst acc '()] (if (nil? bst) (reduce (fn [tree [lr elt branch]] (if (= lr :l) (struct node elt branch tree) (struct node elt tree branch))) (struct node x) acc) (let [elt (:elt bst)] (if (= x elt) bst (if (comp x elt) (recur (:l bst) (cons [:r elt (:r bst)] acc)) (recur (:r bst) (cons [:l elt (:l bst)] acc))))))))Once I had the first tail recursive version, I asked my friend Yogi how he would transform the

(struct node elt l (:r bst))The problem is, when we are doing this operation, we do not know the value of

(defn bst-insert-tc3 [bst x cmp] (loop [bst bst f identity] (if (nil? bst) (f (struct node x)) (let [elt (:elt bst)] (if (= x elt) bst (if (cmp x elt) (recur (:l bst) (comp f (fn [l] (struct node elt l (:r bst))))) (recur (:r bst) (comp f (fn [r] (struct node elt (:l bst) r))))))))))The code shows how functional programming can be both elegant and efficient.

The full code for the BST is available

## No comments:

## Post a Comment