Michael Ummels bio photo

Michael Ummels

Software. Railways. Traveling.

Twitter Github

This tram has just left the depot to make its first run as line M5 to Hauptbahnhof. Due to construction work at Leonhardplatz the direct route to the terminal is blocked and all trams need to go via Schloss, which made this picture possible.

Tram Leonhardstraße at Dawn

Finally, I have decided to get a decent coffee setup for my home. After playing with the thought of buying a real Espresso machine, I finally went for a good grinder (which I could also use with an Espresso machine later) combined with a simple French press, which already gives much better coffee than using a filter with factory ground coffee. I am still on the hunt for the best beans in town, so don’t expect a final verdict anytime soon.

Coffee setup

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.