On Wed, Dec 15, 2010 at 12:49 AM, Todd <t.greenwoodg...@gmail.com> wrote:
> My main question is, what tasks/apps is clojure ideally suited for?
>
> I've been playing with implementing Binary Search Trees in clojure and Java
> as a way to learn clojure and compare the two languages. My original thought
> was to implement some basic data types and algorithms in a handful of
> interesting languages and compare the experience. For me, the list includes
> clojure, java, scala, and erlang.
>
> So far, my experience implementing basic BST functionality in clojure has
> felt contrived, and was definitely easier in java.
>
> Code: https://github.com/ToddG/experimental/tree/master/clojure/algorithms
>
> 1. TreeNode
>
> (defrecord TreeNode [left right key] ...
Perhaps instead of emulating a Java-esque approach you should use
Clojure's native data structures. E.g. a vector
[key left right]
for a node.
In-order traversal is then just
(defn in-order-seq [node]
(let [left (node 1) right (node 2)]
(cons (node 0)
(concat
(if left (in-order-seq left))
(if right (in-order-seq right)))))
"Inserting" a node is
(assoc-in node [1 2 2 1 2] some-new-node)
or similar; in this case, from the root it goes left, right, right,
and left to reach the parent node of the new node, and inserts or
replaces the right child of that parent node; the sequence of 1s and
2s could itself be a generated seq.
Finding the correct position in the tree for something, as such a seq, is then:
(defn pos-of [node k]
(if-not (= (node 0) k)
(let [left (node 1) right (node 2)]
(if (and left (<= k (left 0)))
(cons 1 (pos-of left k))
(if right (cons 2 (pos-of right k))
(if left [2] [1]))))))
Then you can do an insert with a modified pos-of (one traversal) or with
(assoc-in node (pos-of node k) [k nil nil])
and a query with
(get-in node (pos-of node k))
which should produce the node containing k, if any, or nil if there is none.
Of course using just the above won't generally create a *balanced*
tree but it is a start and shows one way to use Clojure's native data
structures to do this kind of thing.
--
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
