Alex Osborne <a...@meshy.org> writes:
> Todd <t.greenwoodg...@gmail.com> writes:
>
>> So far, my experience implementing basic BST functionality in clojure
>> has felt contrived, and was definitely easier in java.
>
> As others have said, implementing mutable data structures in Clojure is
> going against the grain of the language
I took a closer look at your code. It does seem to be persistent but I
was thrown off by what you're doing with the stack and all that looping.
Is the idea that you're worried about stack size, so trying to convert
it to heap usage by using a vector as an explicit stack? I guess that's
a fair point with an unbalanced tree.
I took a stab at a persistent version as well. I extended
IPersistentSet so it behaves naturally with all of Clojure's collection
functions. I also took the shortcut and just used recursion. It will
sadly stack overflow for a large unbalanced tree (probably better to
implement a red black tree for real work anyway).
The laziness of "concat" seems to make traversal really easy. I
went with inorder traversal for "seq" but that's really simple to change:
Preorder: (concat [el] l r)
Inorder: (concat l [el] r)
Postorder: (concat l r [el])
You could of course define a new protocol that has a variant of the
"seq" function for the different traversal orders.
To apply a visitor function: (map f bst).
Here's the code. I'm not totally happy with this: "cons" could
definitely do with some refactoring. I also got a bit slack with the
last cond case in "disjoin". Not hugely tested either.
(declare empty-bst)
(deftype PersistentBST [el l r]
clojure.lang.IPersistentSet
(empty [this] empty-bst)
(seq [this] (concat l [el] r))
(disjoin [this k]
(let [rel (compare k el)]
(cond (neg? rel) (PersistentBST. el (disj l k) r)
(pos? rel) (PersistentBST. el l (disj r k))
(and (empty? l) (empty? r)) empty-bst
(empty? l) r
(empty? r) l
:else (let [smallest (first r)]
(PersistentBST. smallest l
(disj r smallest))))))
(contains [this k]
(let [rel (compare k el)]
(cond (neg? rel) (contains? l k)
(pos? rel) (contains? r k)
:else true)))
(get [this k]
(let [rel (compare k el)]
(cond (neg? rel) (get l k)
(pos? rel) (get r k)
:else el)))
(cons [this x]
(let [rel (compare x el)]
(cond (neg? rel) (PersistentBST.
el (if l
(conj l x)
(PersistentBST. x empty-bst empty-bst))
r)
(pos? rel) (PersistentBST.
el l (if r
(conj r x)
(PersistentBST. x empty-bst empty-bst)))
:else this)))
(count [this]
(inc (+ (if l (count l) 0)
(if r (count r) 0))))
(equiv [this o]
(and (instance? PersistentBST o)
(let [^PersistentBST o o]
(and (= el (.el o))
(= l (.l o))
(= r (.r o)))))))
(deftype EmptyPersistentBST []
clojure.lang.IPersistentSet
(empty [this] empty-bst)
(seq [this] nil)
(disjoin [this k] empty-bst)
(contains [this k] false)
(get [this k] nil)
(cons [this x] (PersistentBST. x empty-bst empty-bst))
(count [this] 0)
(equiv [this o] (instance? EmptyPersistentBST o)))
(def empty-bst (EmptyPersistentBST.))
Some example usage:
(def bst (into empty-bst [7 1 7 2 9]))
bst ;; => #{1 2 7 9}
(count bst) ;; => 4
(disj bst 9) ;; => #{1 2 7}
(get bst 1) ;; => 1
(contains? bst 2) ;; => true
(seq bst) ;; => (1 2 7 9)
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
