I came across a handy tool named xdootool. It simulates keyboard or mouse presses and sends them to a window.

The following bash script sends a reload command to a window named Jasmine Spec Runner every time a file is changed in the directories src and spec.

#!/bin/bash

while true; do
    xdotool search --name "Jasmine Spec Runner" key --clearmodifiers "CTRL+R";
    inotifywait -r -qq -e modify -e delete src spec;
done

Both xdotool and inotifywait work on Linux based systems. However, equivalent tools or ports may exist for Windows or Mac OS X.

To illustrate this point, I’ll use the following example: An ordered list of dates is processed until a specified date. To each matching date a function is applied. In addition, the results of the function calls are accumulated and returned.

My first attempt is shown below:

(ns accumulator.core
  (:require [clj-time.core :as t]))

(def all-dates (reverse (map #(t/date-time 2013 %) (range 1 13))))

(defn get-month [date]
  (t/month date))

(defn process-dates-accumulator [all-dates until f]
  (loop [dates all-dates
         result []]
    (if (t/before? (first dates) until)
      result
      (recur (rest dates)
             (conj result (f (first dates)))))))

(process-dates-accumulator all-dates (t/date-time 2013 06) get-month)

The process-dates-accumulator iterates over the range of dates. For each date more recent than until the function f is applied. In this example get-month is used. Furthermore, the accumulation is done in results.

Accumulating With reduce

Being a functional language Clojure embraces the use of generic combinator functions like map and reduce.

Consider this implementation of the example described above:

(defn process-dates-reduce [all-dates until f]
  (reduce #(conj %1 (f %2))
          []
          (filter #(not (t/after? until %)) all-dates)))

First, the initial list of dates is filtered to include all candidates. Afterwards, reduce accumulates the results of applying the function f to each candidate.

Conclusion

As shown above standard functions like reduce offers powerful abstractions. The advantage of using these functions is that those are highly optimized. Moreover, they can be applied to a wide range of situations.

I think one way of making things more clear is to visualize the process that is generated by a recursive algorithm.

Fibonacci Numbers

The classical example for introducing recursion is Fibonacci numbers. Consider this implementation in Python:

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

What is interesting about this algorithm is that it generates a process with a tree structure. This is illustrated in the following.

Just by looking at the source code it is hard to reason about its generated process. In contrast, I think the illustration helps.

The picture also shows why this naive implementation is quite slow. A large number of function calls are computed multiple times.

Merge Sort

Another classical recursive algorithm is Merge sort. It is a divide and conquer algorithm that recursively breaks the input down into smaller problems and merges it back in sorted order. The algorithm is implemented like this (full implementation is available here):

def mergesort(lst):
    if len(lst) < 2:
        return lst
    middle = len(lst) / 2
    left = mergesort(lst[:middle])
    right = mergesort(lst[middle:])
    return merge(left, right)

The generated process of sorting 9, 1, 4, 6, 3, 2, 7, 8 is shown below.

Constructing All Permutations

The problem of constructing all permutations of a string can be solved recursively. For instance, this implementation:

def permutations(string, rest):
    if len(rest) == 0:
        return [string]

    result = []
    for i in xrange(len(rest)):
        next_rest = [rest[j] for j in xrange(len(rest)) if j != i]
        result.extend(permutations(string + rest[i], ''.join(next_rest)))
    return result

produces the following process for “abc”.

Moreover, the resulting permutations of “abc” reside at the leaves of the process tree: “abc”, “acb”, “bac”, “bca”, “cab” and “cba”.

Conclusion

Of course, there are different strategies that help with understanding recursive processes. I think visualizing the process of a recursive algorithm is very helpful. Especially in the beginning.

Further Reading

• Structure and Interpretation of Computer Programs (especially Section 1.2)
• The Little Schemer
• The Algorithm Design Manual

Server-Side

On the server-side a bare repository has to be created

$ mkdir remote-project.git
$ cd remote-project.git
$ git init --bare

Client-Side

In contrast, on the client side it is now possible to clone the remote repository

$ git clone ssh://user@server/path/to/remote-project.git

Afterwards, changes can be pushed to the server

$ cd remote-project
<add and commit your changes>
$ git push origin master

Which kind of content can you expect to find here? I am planning to write about programming, technology, ideas and things in general I am interested in.

A big thanks to Olli for hosting these pages.

Hopefully, you will find useful information and enjoy reading the articles.