Todd <t.greenwoodg...@gmail.com> writes:
> 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.
As others have said, implementing mutable data structures in Clojure is
going against the grain of the language, just as it would be in any
other opinionated functional language. You'd have much the same
experience with Haskell. (Scala doesn't really count in this way, it's
not opinionated.)
Nevertheless since datatypes and protocols were introduced in Clojure
1.2 you *can* do it if you really need to. You'd never do this in a
normal Clojure program, but you might need to when writing say a data
structure library.
Here's a loose translation of the binary search tree from the textbook
"Foundations of Computer Science: C Edition" by Aho and Ullman. I'm
just going to implement the first two functions: lookup and insert.
Deletion, traversal and so on are much the same, just translate the C
code directly to Clojure.
BIG WARNING: I'm naming this "dangerous" on purpose, it's not thread
safe and is very unclojurish. Do not use this data structure in a
real Clojure program (or in any other language for that matter).
It's very naive and really just plain bad. It is in the textbook to
teach you the basics of trees, not because they recommend you actually
use it.
First up we need a protocol for a node struct with settable left and
right child fields. (Yuck!)
(defprotocol MutableBinaryNode
(element [node])
(left [node])
(right [node])
(set-left! [node x])
(set-right! [node x]))
Now the concrete implementation of the protocol, note that we annotate
the "l" and "r" fields as :unsynchronized-mutable so that we can use
set! on them. (Discouraged!)
(deftype DangerousBinaryNode [el
^{:unsynchronized-mutable true} l
^{:unsynchronized-mutable true} r]
MutableBinaryNode
(element [this] el)
(left [this] l)
(right [this] r)
(set-left! [this x] (set! l x))
(set-right! [this x] (set! r x)))
Next the lookup function. It returns true if the element x is present
in the search tree. This is basically identical to the C code except
I'm using compare instead of < so that you can put strings and other
objects in the BST, not just numbers. A good data structure would also
let you specify an alternative comparator (see Clojure's sorted-set for
example).
(defn- lookup* [node x]
(when node
(let [rel (compare x (element node))]
(cond (zero? rel) true
(neg? rel) (recur (left node) x)
(pos? rel) (recur (right node) x)))))
Again insert is almost identical to the C code, just using a constructor
instead of malloc:
(defn- insert* [node x]
(if (nil? node)
(DangerousBinaryNode. x nil nil)
(let [rel (compare x (element node))]
(cond (neg? rel) (set-left! node (insert* (left node) x))
(pos? rel) (set-right! node (insert* (right node) x)))
node)))
Finally for usage convenience and so that we can have an empty
BST, let's wrap that in a public API. All the above is implementation
detail and shouldn't be exposed by a library.
(defprotocol MutableSet
(lookup [coll x])
(insert! [coll x]))
(deftype DangerousBST [^{:unsynchronized-mutable true} root]
MutableSet
(lookup [this x] (lookup* root x))
(insert! [this x] (set! root (insert* root x))))
(defn dangerous-bst [] (DangerousBST. nil))
Now we can try it out:
(def bst (dangerous-bst))
(insert! bst 1)
(insert! bst 7)
(lookup bst 1) ;; -> true
(lookup bst 4) ;; -> nil
(lookup bst 7) ;; -> true
--
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
