To set the tone for future posts, today I’d like to discuss Clojure. In short, Clojure is a Lisp dialect that targets the Java Virtual machine, so you can use all the Java libraries out there. I have been playing with Clojure for a couple of years now, using it at work since last year. To give you a taste of the language, check out this extremely concise implementation of Dijkstra’s shortest-path algorithm:

(require '[clojure.data.priority-map :refer [priority-map]])
 
(defn map-vals [m f]
  (into {} (for [[k v] m] [k (f v)])))
 
(defn remove-keys [m pred]
  (select-keys m (filter (complement pred) (keys m))))
 
(defn dijkstra
  "Computes single-source shortest path distances in a directed graph.

  Given a node n, (f n) should return a map with the successors of n
  as keys and their (non-negative) distance from n as vals.
 
  Returns a map from nodes to their distance from start."
  [start f]
  (loop [q (priority-map start 0) r {}]
    (if-let [[v d] (peek q)]
      (let [dist (-> (f v) (remove-keys r) (map-vals (partial + d)))]
        (recur (merge-with min (pop q) dist) (assoc r v d)))
      r)))

If you neglect the two utility functions, the algorithm ist just five lines long, and the only external dependency used is an implementation of the priority queue, which is central to Dijkstra’s algorithm. The loop here (which is needed because the JVM does not support tail recursion) maintains the queue and a dictionary (hash map) with the result. In every iteration, the the node in the queue with the least distance to start is taken from the queue, and the distances of its successors are updated using the merge-with function, while the node is added to the result set.

It is important to note that all the functions operating on data structures do not modify them directly, but rather return new data structures with the result of the operation. Only when the loop enters a new iteration with recur, the new data structures are rebound to the loop variables.

That’s it for today. If you want to play with Clojure yourself, take a look at 4clojure, where you can learn Clojure through solving problems interactively.